几种排序算法
1. 冒泡排序
冒泡排序的内循环方向是从后往前，或者从下往上。内循环两两比较，小的元素逐渐交换到前面。第1次循环会使得最小的数到正确位置。第2次循环使得次小的数到正确位置...
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。1 def bubblesort(arr): 2 if len(arr)<=1:return arr 3 for i in range(0,len(arr)): # [0,i) have been sorted
4 for j in range(len(arr)-1, i, -1): 5 if arr[j]<arr[j-1]: 6 arr[j],arr[j-1]=arr[j-1],arr[j] 7
8 return arr
这是一种基础版本，注意还有一种改良版本，当元素仅仅前几个值顺序有问题，后面的数都排好序的情况。那么前几次冒泡后整个数组就已经又续了，但是按照算法，i还得取到最后一个元素。这样就使得计算冗余。一种解决方案就是设置一个标记，如果当前次没有交换的话，说明后续也无需交换了，即停止算法。
1 def bubblesort(arr): 2 if len(arr)<=1:return arr 3 flag = True 4 for i in range(0,len(arr)): # [0,i) have been sorted
5 if flag: 6 flag=False # 设为FALSE
7 for j in range(len(arr)-1, i, -1): 8 if arr[j]<arr[j-1]: 9 arr[j],arr[j-1]=arr[j-1],arr[j] 10 flag=True # 如果当前有交换则设为True，否则此行代码不执行。下一轮直接break
11 else: 12 break
13
14 return arr
2. 选择排序
思路：每次选择当前元素后面最小的一个数和当前元素替换。
1 def selectsort(arr): 2 if len(arr)<=1:return arr 3 for i in range(len(arr)): 4 index = i 5 for j in range(i+1,len(arr)): 6 if arr[j]<arr[index]: 7 index=j 8 arr[i],arr[index] = arr[index],arr[i] 9
10 return arr
3. 插入排序
思路：每次对当前的元素插入到前面的合适位置。下图2要插入到6之前。
两种操作：先记录temp=2，然后8右移，6右移，再将temp放入。或者2与8交换，2与6交换，结束。
操作1：挪动（更优）
1 def selectsort(arr): 2 if len(arr)<=1:return arr 3 for i in range(1,len(arr)): # [0,i) have been sorted 注意初始值，考虑到[0，1）左闭右开是有序的，所以从1开始
4 index = i-1
5 temp = arr[i] 6 while (index>=0) and (arr[index]>temp): 7 arr[index+1] = arr[index] # 这里是挨个往后挪，也可以用交换的形式 8 index-=1
9 arr[index+1] = temp 10
11 return arr
操作2：交换
1 def selectsort(arr): 2 if len(arr)<=1:return arr 3 for i in range(1,len(arr)): # [0,i) have been sorted
4 index = i-1
5 temp = arr[i] 6 while (index>=0) and (arr[index]>temp): 7 arr[index+1],arr[index] = arr[index],arr[index+1] 8 index-=1
9
10 return arr
总结：操作2每次交换都伴随3次赋值，所以操作1更快一些。插入排序对于近乎有序的数组非常快，极其高效！因为在内层循环中，找到合理位置就立即结束，基本上内层执行几步就结束。虽然插入排序也是O（n^2），在近乎有序数组排序甚至可以达到O（n）的效率。
4. 快速排序
详细分析见另一篇博客：
1 def paitition(arr): # pritition 快排核心思想：在v的左边元素都小于v，v右边元素都大于v
2 if not arr: return None 3 v = arr[0] # 取第一个元素作为pivot元素 4 j = 0 # [l+1,j]>v [j+1,i)>v
5 for i in range(len(arr)): 6 if arr[i]<v: # 当前元素小于v则交换
7 arr[j+1],arr[i] = arr[i],arr[j+1] 8 j=j+1
9 arr[0],arr[j] = arr[j],arr[0] # 最后将该首位元素pivot交换到合理位置
10 return j,arr 11
12
13 def quicksort(arr): # 快速排序主体（递归函数）
14 if len(arr)<=1:return arr # 如果小于2个元素则直接返回
15
16 index,arr = paitition(arr) # 找到pivot元素和位置
17 arr[0:index] = quicksort(arr[0:index]) # 排序pivot左半部分
18 arr[index+1:len(arr)] = quicksort(arr[index+1:len(arr)]) # 排序pivot元素右部分
20 return arr
22
23 print(quicksort([0,1,2,0,3,2,4,2,402,0])) # 测试快排
快速排序的最坏复杂度是O（n^2） 。考虑数组为正序或逆序，当每次在最左边选择的元素作为标定点时，每次划分的两个子序列一个为空，另一个非空。这就导致用递归树画出来是一颗斜树。复杂度为O(n^2)。当每次划分partition较为均匀时，得到的是最好的情况是O（nlogn）。利用随机选取标定点可以大大降低这种风险。此外快速排序在含大量重复元素时表现也很糟，关于分析和解法（三路快排）见博客。
5. 归并排序
类似于快速排序，归并也是两个子函数：主函数递归+核心操作。
1 def merge(arr1,arr2): # 归并核心思想：合并两个有序的序列 2 if not arr1:return arr2 3 if not arr2:return arr1 4 arr = [] # 开辟一个辅助空间 5 while(arr1 and arr2): 6 if arr1[0]<arr2[0]: 7 arr.append(arr1.pop(0)) 8 else: 9 arr.append(arr2.pop(0)) 10 if arr1:arr.extend(arr1) 11 if arr2:arr.extend(arr2) 12
13 return arr 14
15
16 def mergesort(arr): # 归并函数主体（递归函数） 17 if len(arr)<=1:return arr 18 if len(arr)==2:return [arr[0],arr[1]] if arr[0]<arr[1] else [arr[1],arr[0]] 19
20 mid = int(len(arr)/2) # 一分为2,自顶向下的排序 21 arr1 = mergesort(arr[0:mid]) # 对左边做归并，返回有序的左序列 22 arr2 = mergesort(arr[mid:len(arr)]) # 对右边做归并，返回有序的有序列 23 arr = merge(arr1, arr2) # 合并两个有序数组 24 return arr 25
26
27 print(mergesort([0,0,0.01,1,0,-1,0,1,1111,6,666]))
优化1： 在合并两个近乎有序的数组，在merge时可先判定一下，如果要merge的两个数组第一个数组的最后一个元素还比第二个元素的第1个元素小，那就不用判断了，直接拼接即可。
1 def merge(arr1,arr2): 2 if not arr1:return arr2 3 if not arr2:return arr1 4 arr = [] 5 while(arr1 and arr2): 6 if arr1[0]<arr2[0]: 7 arr.append(arr1.pop(0)) 8 else: 9 arr.append(arr2.pop(0)) 10 if arr1:arr.extend(arr1) 11 if arr2:arr.extend(arr2) 12 13 return arr 14 15 16 def mergesort(arr): 17 if len(arr)<=1:return arr 18 if len(arr)==2:return [arr[0],arr[1]] if arr[0]<arr[1] else [arr[1],arr[0]] 19 20 mid = int(len(arr)/2) 21 arr1 = mergesort(arr[0:mid]) 22 arr2 = mergesort(arr[mid:len(arr)]) 23 if arr1[-1]>arr2[0]: 24 arr = merge(arr1, arr2) 25 else: arr = arr1+arr2 26 return arrView Code
优化2：将上面自顶向下的排序转换为自底向上的算法（迭代，没有利用递归）。思路：首先对单个做归并，然后对两个一组做归并，然后每4个一组做归并...
1 def merge(arr1,arr2): # 子函数不变 2 if not arr1:return arr2 3 if not arr2:return arr1 4 arr = [] 5 while(arr1 and arr2): 6 if arr1[0]<arr2[0]: 7 arr.append(arr1.pop(0)) 8 else: 9 arr.append(arr2.pop(0)) 10 if arr1:arr.extend(arr1) 11 if arr2:arr.extend(arr2) 12
13 return arr 14
15
16 def mergesortBU(arr): 17 sz = 1 # 第一次区间为1，第二次为2，第三次为4...
18 while(sz< len(arr)): 19 i = 0 20 while(i <len(arr)-sz+1): # 原本是(i<len(arr)) 修改得到，因为下面有索引arr[i+sz]
21 arr[i:min(i+sz+sz,len(arr))] = merge(arr[i:i+sz],arr[i+sz:min(i+sz+sz,len(arr))]) 22 # 上面的索引原本是i+sz+sz，但为防止越界，取min操作
23 i = i+sz+sz # 子区间索引
24 sz = sz+sz # 区间加倍
25 return arr 26
27
28 print(mergesortBU([0,0,0.01,1,0,-1,0,1,1111,6,666]))
更多精彩
