10大排序算法python实现
2022/1/11 17:05:58
本文主要是介绍10大排序算法python实现,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
目录- 10大经典排序算法python实现
- 1.冒泡排序
- 2.选择排序
- 3.插值排序
- 4.希尔排序
- 5.归并排序
- 6.快排
- 7.堆排序
- 8.计数排序
- 9.桶排序
- 10.基数排序
10大经典排序算法python实现
1.冒泡排序
#算法思想:每次比较相邻的两个元素,较大的值放后面 #1,每次循环都有一个最大值被排好序了 #2,每次都是从头开始再一次比较,但是需要被比较的次数又少了一次
def bubble_sort(raw_list): length = len(raw_list) for i in range(length-1): #这里首先要判断一共可能会循环几次,因为每次循环都有一个最大值被放到最后,所以最多循环n-1次就能排序完成 print(f'第{i}次') for j in range(length-1-i): #因为循环了i次就排好了i个最大值,所以再循环时需要比较的次数就少了i,结果就是再需要比较n-1-i次 if raw_list[j]>raw_list[j+1]: raw_list[j],raw_list[j + 1] = raw_list[j+1],raw_list[j] #python的交叉赋值语法 print(raw_list) return raw_list
算法排序过程 假设待排序的序列为list0 = [3, 7, 5, 8, 4, 9, 0, 1, 2, 6] """ 第0次 [3, 5, 7, 8, 4, 9, 0, 1, 2, 6] [3, 5, 7, 4, 8, 9, 0, 1, 2, 6] [3, 5, 7, 4, 8, 0, 9, 1, 2, 6] [3, 5, 7, 4, 8, 0, 1, 9, 2, 6] [3, 5, 7, 4, 8, 0, 1, 2, 9, 6] [3, 5, 7, 4, 8, 0, 1, 2, 6, 9] 第1次 [3, 5, 4, 7, 8, 0, 1, 2, 6, 9] [3, 5, 4, 7, 0, 8, 1, 2, 6, 9] [3, 5, 4, 7, 0, 1, 8, 2, 6, 9] [3, 5, 4, 7, 0, 1, 2, 8, 6, 9] [3, 5, 4, 7, 0, 1, 2, 6, 8, 9] 第2次 [3, 4, 5, 7, 0, 1, 2, 6, 8, 9] [3, 4, 5, 0, 7, 1, 2, 6, 8, 9] [3, 4, 5, 0, 1, 7, 2, 6, 8, 9] [3, 4, 5, 0, 1, 2, 7, 6, 8, 9] [3, 4, 5, 0, 1, 2, 6, 7, 8, 9] 第3次 [3, 4, 0, 5, 1, 2, 6, 7, 8, 9] [3, 4, 0, 1, 5, 2, 6, 7, 8, 9] [3, 4, 0, 1, 2, 5, 6, 7, 8, 9] 第4次 [3, 0, 4, 1, 2, 5, 6, 7, 8, 9] [3, 0, 1, 4, 2, 5, 6, 7, 8, 9] [3, 0, 1, 2, 4, 5, 6, 7, 8, 9] 第5次 [0, 3, 1, 2, 4, 5, 6, 7, 8, 9] [0, 1, 3, 2, 4, 5, 6, 7, 8, 9] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 第6次 第7次 第8次 """
2.选择排序
#算法思想:每次遍历都找到一个最小的元素拿到前面 #1,从第一个元素开始和后面的元素比较,如果小就记录位置,然后拿这个记录位置的较小元素继续和后面的比较,如果更小的就记录这个更小的位置,一直到该轮循环结束 #2,一轮循环下来就会得到一个最小值得位置,拿这个最小值位置的值和循环开始的值交换
def selection_sort(raw_list): length = len(raw_list) for i in range(length-1): print(f'第{i}次') minindex = i for j in range(i+1,length): if raw_list[minindex] > raw_list[j]: minindex = j #每次记录最小值的位置 if i != minindex: raw_list[i],raw_list[minindex] = raw_list[minindex],raw_list[i] #一轮循环结束之后把最小值的位置和循环开始位置交换 print(raw_list) return raw_list
算法排序过程 假设待排序的序列为list0 = [3, 7, 5, 8, 4, 9, 0, 1, 2, 6] """ 第0次 [0, 7, 5, 8, 4, 9, 3, 1, 2, 6] 第1次 [0, 1, 5, 8, 4, 9, 3, 7, 2, 6] 第2次 [0, 1, 2, 8, 4, 9, 3, 7, 5, 6] 第3次 [0, 1, 2, 3, 4, 9, 8, 7, 5, 6] 第4次 第5次 [0, 1, 2, 3, 4, 5, 8, 7, 9, 6] 第6次 [0, 1, 2, 3, 4, 5, 6, 7, 9, 8] 第7次 第8次 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] """
3.插值排序
#算法思想:假设我有一堆已经排序好的序列,现在又给我一个值,我只需要把这个值放到合适的位置就行了(这里和冒泡排序类似) #现在我有一堆无序的数列,那么第一个值肯定是有序的(一个值就是有序的) #然后拿第二个值放到第一个后面这时组成的序列就变的无序了,把刚拿到的值和第一个值排序,得到有序的序列 #再拿第三个值和前两个值放一起,然后再把第三个值和前两个值排序,以此类推
def insert_sort(raw_list): length = len(raw_list) for i in range(1,length): print(f'第{i}次') for j in range(i,0,-1): if raw_list[j]<raw_list[j-1]: raw_list[j], raw_list[j-1] = raw_list[j-1], raw_list[j] print(raw_list) else:#这里如果添加的这个值比最大的值还大,就没必要继续忘下比较了 continue
算法排序过程 假设待排序的序列为list0 = [3, 7, 5, 8, 4, 9, 0, 1, 2, 6] """ 第1次 第2次 [3, 5, 7, 8, 4, 9, 0, 1, 2, 6] 第3次 第4次 [3, 5, 7, 4, 8, 9, 0, 1, 2, 6] [3, 5, 4, 7, 8, 9, 0, 1, 2, 6] [3, 4, 5, 7, 8, 9, 0, 1, 2, 6] 第5次 第6次 [3, 4, 5, 7, 8, 0, 9, 1, 2, 6] [3, 4, 5, 7, 0, 8, 9, 1, 2, 6] [3, 4, 5, 0, 7, 8, 9, 1, 2, 6] [3, 4, 0, 5, 7, 8, 9, 1, 2, 6] [3, 0, 4, 5, 7, 8, 9, 1, 2, 6] [0, 3, 4, 5, 7, 8, 9, 1, 2, 6] 第7次 [0, 3, 4, 5, 7, 8, 1, 9, 2, 6] [0, 3, 4, 5, 7, 1, 8, 9, 2, 6] [0, 3, 4, 5, 1, 7, 8, 9, 2, 6] [0, 3, 4, 1, 5, 7, 8, 9, 2, 6] [0, 3, 1, 4, 5, 7, 8, 9, 2, 6] [0, 1, 3, 4, 5, 7, 8, 9, 2, 6] 第8次 [0, 1, 3, 4, 5, 7, 8, 2, 9, 6] [0, 1, 3, 4, 5, 7, 2, 8, 9, 6] [0, 1, 3, 4, 5, 2, 7, 8, 9, 6] [0, 1, 3, 4, 2, 5, 7, 8, 9, 6] [0, 1, 3, 2, 4, 5, 7, 8, 9, 6] [0, 1, 2, 3, 4, 5, 7, 8, 9, 6] 第9次 [0, 1, 2, 3, 4, 5, 7, 8, 6, 9] [0, 1, 2, 3, 4, 5, 7, 6, 8, 9] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] """
4.希尔排序
#为什么会有希尔排序:插值排序对比较有序的数组排序时效率会高很多 #算法思想:先将整个数据分成多组,然后对组内数据进行插值排序,循环前面的步骤, #注意:每次分组,组内元素越来越多(也就是说组数越来越少),直到把所有数据都分成一组,这样所有的数据基本就有序了然后再进行插值排序
def shell_sort(row_list): length = len(row_list) group = length//2 #先把两个数据分到一组,下次把4个数据分到一组,下次8个,32个.... count=1 while group>0: #组会越来越小直到group为1时结束 print(f'分组个数:{group}') print(f'第{count}次') for i in range(0,group): #要把每一组的都跑一遍 j=i while j<length-group: #每一组里面可能有多个元素,元素之间的索引位置相差一个group,这里要对这一组元素进行差值排序,防止索引越界的问题 if row_list[j]>row_list[j+group]: row_list[j], row_list[j + group] = row_list[j + group], row_list[j] print(row_list) j += group #元素之间的索引位置相差一个group group = group//2 #下次把4个数据分到一组,下次8个,32个.... count+=1
算法排序过程 假设待排序的序列为list0 = [3, 7, 5, 8, 4, 9, 0, 1, 2, 6] """ 分组个数:5 第1次 [3, 0, 5, 8, 4, 9, 7, 1, 2, 6] [3, 0, 1, 8, 4, 9, 7, 5, 2, 6] [3, 0, 1, 2, 4, 9, 7, 5, 8, 6] 分组个数:2 第2次 [1, 0, 3, 2, 4, 9, 7, 5, 8, 6] [1, 0, 3, 2, 4, 5, 7, 9, 8, 6] [1, 0, 3, 2, 4, 5, 7, 6, 8, 9] 分组个数:1 第3次 [0, 1, 3, 2, 4, 5, 7, 6, 8, 9] [0, 1, 2, 3, 4, 5, 7, 6, 8, 9] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] """
5.归并排序
#归并排序利用了分而治的思想:递的时候分(拆分),归的时候治(排序+并),注意与快排的区别
def merge(l1,l2): """ 排序逻辑,递归归来的时候调用改方法 """ res_list = [] print(f'归-待治:{l1},{l2}') #两个有序的列表怎么才能合成一个有序的列表呢? while l1 and l2: if l1[0] <= l2[0]: res_list.append(l1.pop(0)) else: res_list.append(l2.pop(0)) while l1: res_list.append(l1.pop(0)) while l2: res_list.append(l2.pop(0)) print(f'归-已治:{res_list}') return res_list def merge_sort(row_list): #第一步:分,每次把数据分成两份直到不能再分为止 length = len(row_list) if len(row_list)<2: return row_list mid = length // 2 ll = row_list[:mid] lr = row_list[mid:] print(f'递:左{ll},右{lr}') # 第二步:治,每往回退一层就 合并+排序 一次 return merge(merge_sort(ll),merge_sort(lr)) #归并排序的精髓在这里, # 1.在归的时候再排序,由于递的时候都是把元素分为单个值.单个值就是有序的, # 2.所以归的时候的任务就是把两个有序的列表合并为一个列表
算法排序过程 假设待排序的序列为list0 = [3, 7, 5, 8, 4, 9, 0, 1, 2, 6,10] """ 递:左[3, 7, 5, 8, 4],右[9, 0, 1, 2, 6, 10] 递:左[3, 7],右[5, 8, 4] 递:左[3],右[7] 归-待治:[3],[7] 归-已治:[3, 7] 递:左[5],右[8, 4] 递:左[8],右[4] 归-待治:[8],[4] 归-已治:[4, 8] 归-待治:[5],[4, 8] 归-已治:[4, 5, 8] 归-待治:[3, 7],[4, 5, 8] 归-已治:[3, 4, 5, 7, 8] 递:左[9, 0, 1],右[2, 6, 10] 递:左[9],右[0, 1] 递:左[0],右[1] 归-待治:[0],[1] 归-已治:[0, 1] 归-待治:[9],[0, 1] 归-已治:[0, 1, 9] 递:左[2],右[6, 10] 递:左[6],右[10] 归-待治:[6],[10] 归-已治:[6, 10] 归-待治:[2],[6, 10] 归-已治:[2, 6, 10] 归-待治:[0, 1, 9],[2, 6, 10] 归-已治:[0, 1, 2, 6, 9, 10] 归-待治:[3, 4, 5, 7, 8],[0, 1, 2, 6, 9, 10] 归-已治:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] """
6.快排
#快排也利用了分而治的思想:递的时候又分又治(拆分+排序),归的时候合并就行了
def merger(left,m,right): return quick_sort(left)+m+quick_sort(right) def quick_sort(row_list): if len(row_list)<=1: return row_list length = len(row_list) mid = length//2 right = [i for i in row_list if i>row_list[mid]] left = [i for i in row_list if i<row_list[mid]] m = [i for i in row_list if i==row_list[mid]] print(f'递:左{left}:,中{m}:,右{right}') return merger(left,m,right) #左和右都是已经排好序的列表,归的时候只需要合并就行了
7.堆排序
#利用堆的性质排序,其实这里用的堆是一颗完全二叉树(如果某个节点的子节点不满2个就不会有下一层,不足一层的子节点依左边对齐) #如何把列表看成对呢:其实堆的编号是2^0,2^1,2^2...依次增加的,把列表的索引看成是堆的编号,列表就成了堆
def max_heap(row_list,n,maxid): i = maxid #节点自己的编号 l = 2*maxid+1 #左子节点编号 r = l+1 #右子节点编号 if l<n and row_list[l]>row_list[maxid]: maxid = l if r<n and row_list[r]>row_list[maxid]: maxid = r if maxid != i: row_list[i],row_list[maxid] = row_list[maxid],row_list[i] print(maxid) print(row_list) #这里一旦调整了节点那么要递归的把改动的节点都要再比较一遍 max_heap(row_list,n,maxid) def heap_sort(row_list): n = len(row_list) #1创建大根堆 for i in range(n-1,-1,-1):#这里的i开始其实可是设置成n//2,因为n>n//2时节点是没有子节点的 max_heap(row_list,n,i) #2对调首位位置继续创建大根堆 for i in range(n-1,-1,-1): row_list[0],row_list[i] = row_list[i],row_list[0] print(f'剩下的元素对调首尾:{row_list}') max_heap(row_list, i, 0) #这里每次循环列表末尾的元素都是已经排序好的,都不计算在内 return row_list
算法排序过程 假设待排序的序列为list0 = [3, 7, 5, 8, 4, 9, 0, 1, 2, 6,10] """ 10 [3, 7, 5, 8, 10, 9, 0, 1, 2, 6, 4] 5 [3, 7, 9, 8, 10, 5, 0, 1, 2, 6, 4] 4 [3, 10, 9, 8, 7, 5, 0, 1, 2, 6, 4] 1 [10, 3, 9, 8, 7, 5, 0, 1, 2, 6, 4] 3 [10, 8, 9, 3, 7, 5, 0, 1, 2, 6, 4] 剩下的元素对调首尾:[4, 8, 9, 3, 7, 5, 0, 1, 2, 6, 10] 2 [9, 8, 4, 3, 7, 5, 0, 1, 2, 6, 10] 5 [9, 8, 5, 3, 7, 4, 0, 1, 2, 6, 10] 剩下的元素对调首尾:[6, 8, 5, 3, 7, 4, 0, 1, 2, 9, 10] 1 [8, 6, 5, 3, 7, 4, 0, 1, 2, 9, 10] 4 [8, 7, 5, 3, 6, 4, 0, 1, 2, 9, 10] 剩下的元素对调首尾:[2, 7, 5, 3, 6, 4, 0, 1, 8, 9, 10] 1 [7, 2, 5, 3, 6, 4, 0, 1, 8, 9, 10] 4 [7, 6, 5, 3, 2, 4, 0, 1, 8, 9, 10] 剩下的元素对调首尾:[1, 6, 5, 3, 2, 4, 0, 7, 8, 9, 10] 1 [6, 1, 5, 3, 2, 4, 0, 7, 8, 9, 10] 3 [6, 3, 5, 1, 2, 4, 0, 7, 8, 9, 10] 剩下的元素对调首尾:[0, 3, 5, 1, 2, 4, 6, 7, 8, 9, 10] 2 [5, 3, 0, 1, 2, 4, 6, 7, 8, 9, 10] 5 [5, 3, 4, 1, 2, 0, 6, 7, 8, 9, 10] 剩下的元素对调首尾:[0, 3, 4, 1, 2, 5, 6, 7, 8, 9, 10] 2 [4, 3, 0, 1, 2, 5, 6, 7, 8, 9, 10] 剩下的元素对调首尾:[2, 3, 0, 1, 4, 5, 6, 7, 8, 9, 10] 1 [3, 2, 0, 1, 4, 5, 6, 7, 8, 9, 10] 剩下的元素对调首尾:[1, 2, 0, 3, 4, 5, 6, 7, 8, 9, 10] 1 [2, 1, 0, 3, 4, 5, 6, 7, 8, 9, 10] 剩下的元素对调首尾:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 1 [1, 0, 2, 3, 4, 5, 6, 7, 8, 9, 10] 剩下的元素对调首尾:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 剩下的元素对调首尾:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] """
8.计数排序
#计数排序有使用条件限制,值不为小数,且知道最大值最小值,这里假设最小值为0 #生产最大值和最小值整数区间,循环列表的元素把对应的整数计数加一,元素循环一遍之后把计数区间按计数个数展开
def count_sort(row_list): max_value = max(row_list) dic = {i:0 for i in range(0,max_value+1)} for num in row_list: dic[num]+=1 res_list = [] print(dic) for key in dic: temp_list = dic[key]*[key] res_list.extend(temp_list) return res_list
9.桶排序
# 计数排序的升级版,知道最大值最小值,这里假设最小值为0
def bucket_sort(row_list): max_value = max(row_list) #1确定桶的大小,可以用(最大值-最小值)/元素个数,我们用于演示,这里随便定一个值4,那么桶的个数就是最大值//3+1 size = 4 bucket = max_value//size #桶的个数一单确定那么每个桶的区间就确定了 bucket_list = [[] for i in range(bucket+1)] #2把元素放到对应的桶中 for num in row_list: bucket_id = num//size #用元素值除以桶的大小来确定该元素该放到那个桶 bucket_list[bucket_id].append(num) print(bucket_list) #3桶内排序,随便使用一种排序算法,这里直接调用python自带的排序函数 res_list = [] for bucket in bucket_list: bucket.sort() # 4把桶内的数据展开 res_list.extend(bucket) return res_list
算法排序过程 假设待排序的序列为list0 = [3, 7, 5, 8, 4, 9, 0, 1, 2, 6,10] """ [[3], [], []] [[3], [7], []] [[3], [7, 5], []] [[3], [7, 5], [8]] [[3], [7, 5, 4], [8]] [[3], [7, 5, 4], [8, 9]] [[3, 0], [7, 5, 4], [8, 9]] [[3, 0, 1], [7, 5, 4], [8, 9]] [[3, 0, 1, 2], [7, 5, 4], [8, 9]] [[3, 0, 1, 2], [7, 5, 4, 6], [8, 9]] [[3, 0, 1, 2], [7, 5, 4, 6], [8, 9, 10]] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] """
10.基数排序
#和桶排序类似,这里桶的个数固定10个, #最大值有几位就循环几次,第i次就除以10**i,对10取余放入对应的桶桶中,合并第i次排序的结果进入下一次循环
def radix_sort(row_list): max_value = max(row_list) n = len(str(max_value)) for i in range(n): print(f'第{i+1}次') bucket = 10 bucket_list = [[] for i in range(bucket)] for value in row_list: bucket_id = (value//10**i)%10 bucket_list[bucket_id].append(value) print(bucket_list) row_list = [i for _list in bucket_list for i in _list] #将桶内的数据按循序展开 print(row_list) # row_list = [] # for _list in bucket_list: # row_list.extend(_list) return row_list
算法排序过程 假设待排序的序列为list0 = [3, 7, 5, 8, 4, 9, 0, 1, 2, 6,10] """ 第1次 [[0, 10], [1], [2], [3], [4], [5], [6], [7], [8], [9]] [0, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9] 第2次 [[0, 1, 2, 3, 4, 5, 6, 7, 8, 9], [10], [], [], [], [], [], [], [], []] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] """
这篇关于10大排序算法python实现的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-02Python编程基础
- 2024-11-01Python 基础教程
- 2024-11-01用Python探索可解与不可解方程的问题
- 2024-11-01Python编程入门指南
- 2024-11-01Python编程基础知识
- 2024-11-01Python编程基础
- 2024-10-31Python基础入门:理解变量与数据类型
- 2024-10-30Python股票自动化交易资料详解与实战指南
- 2024-10-30Python入行:新手必读的Python编程入门指南
- 2024-10-30Python入行:初学者必备的编程指南