数据结构——排序（python实现）

最近开始学习王争老师的《数据结构与算法之美》，通过总结再加上自己的思考的形式记录这门课程，文章主要作为学习历程的记录。

最常见的排序方法有：冒泡排序、插入排序、选择排序、快速排序、计数排序、基数排序、桶排序等。按时间复杂度将其分为：

排序算法时间复杂度是否基于比较冒泡、插入、选择O($n^2$)√快排、归并O($nlogn$)√桶、计数、基数O($n$)×

分析排序算法的执行效率，需要从以下几个方面衡量： 1.最好情况，最坏情况，平均情况时间复杂度 2.时间复杂度的系数，常数，低阶 3.比较次数和交换（或移动）次数

排序算法的内存消耗

算法的内存消耗可以通过空间复杂度来衡量，排序算法也不例外。针对排序算法的空间复杂度，引入了一个新的概念——原地排序。这种算法特指空间复杂度是O(1)的排序算法。冒泡，插入，选择排序都是原地排序算法。

排序算法的稳定性

如果序列中有两个存在值相等的元素，经过排序之后，若其先后顺序不变，则称为稳定的排序算法。如果发生变化，则称为不稳定的排序算法。

冒泡排序

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求，不满足则互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复n次，就完成了n个数据的排序工作。 以4，5，6，3，2，1为例

经过一次冒泡操作之后，6这个元素已经存储在正确的位置上。要想完成所有数据的排序，我们只要进行6次这样的冒泡操作。冒泡操作还可以继续优化。当某次冒泡操作已经没有数据交换时，说明已经达到有序，不再需要进行下一次了。

结论：

①冒泡排序是原地排序算法 ②冒泡排序是稳定的排序算法 ③冒泡排序的最好情况时间复杂度是O(n)，最坏情况时间复杂度为O($n^2$)，分析平均情况时间复杂度需要考虑有序度和逆序度。最坏情况下有序度为0，需进行$n\ast (n-1)/2$。最好情况下有序度为$n\ast (n-1)/2$，不需要交换，不进行严格推导，我们取中间值$n\ast (n-1)/4$。故平均时间复杂度为O($n^2$)。

#冒泡排序 l = [4,7,6,8,3,2,8] l_len = len(l) t = 0 for i in range(l_len): flag = 0 for j in range(l_len-1): t += 1 #循环次数 if l[j]>l[j+1]: l[j+1],l[j] = l[j],l[j+1] flag = 1 else: continue if flag == 0: break print(l,t)

插入排序

一个有序的数组，往里面添加一个新的数据后，如何继续保持数据有序？只需要遍历数组，找到数组应该插入的位置插入即可。

这是一种动态排序的方法，即动态往有序集合中添加数据。对于一组静态数据，可以借鉴上面的插入方法进行排序，就有了插入排序算法。

执行插入排序操作时，我们将数组中的数据分为两个区间，已排序区间和未排序区间。插入算法的核心思想是取未排序区间的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序，重复这个过程，直到未排序区间中元素为空，算法结束。如图，要排序的数据为4，5，6，1，3，2，左侧为已排序区间，右侧为未排序区间。

插入排序也包含两种操作，一种是元素的比较，一种是元素的移动，需要将a插入已排序区间时，需要拿a与已排序区间元素依次比较大小，找到合适的插入位置。找到插入点后，需要将插入点之后的元素往后移一位，腾出位置给元素a插入。

对于一个给定的初始序列，移动次数是固定的，就等于逆序数。

结论：

①插入排序是原地排序算法 ​②插入排序是稳定的排序算法 ③插入排序最好情况时间复杂度是O(n)，最坏情况时间复杂度是O($n^2$)，平均时间复杂度为O($n^2$)

#插入排序 l = [4,7,6,8,3,2,8,7,2,4,1,0] l_len = len(l) for i in range(1,l_len): if i == 1 and l[i]<l[i-1]: l[i],l[i-1]=l[i-1],l[i] if l[i]<l[i-1] and i>1: for j in range(0,i-1): if l[i]<=l[j+1] and l[i]>l[j]: l[j+1],l[j+2:i+1] = l[i],l[j+1:i] break elif l[i]<=l[0]: l[0],l[1:i+1] = l[i],l[0:i] break else: continue print(l)

选择排序

选择排序算法实现思路有点类似于插入排序，也分已排序区间和未排序区间，但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。如图：

结论：

①选择排序是一种原地排序算法 ②选择排序是一种不稳定排序算法，以5，8，5，2，9为例，两个5的顺序会发生改变 ③选择排序的最好时间复杂度，最坏时间复杂度和平均时间复杂度均为O($n^2$)

对上面三种排序方法做一个比较：

是否原地排序是否稳定最好时间复杂度最坏时间复杂度平均时间复杂度冒泡排序√√O(n)O($n^2$)O($n^2$)插入排序√√O(n)O($n^2$)O($n^2$)选择排序√×O($n^2$)O($n^2$)O($n^2$)

其中，插入排序速度要快于冒泡排序。

介绍完三种时间复杂度为O($n^2$)的排序算法，它们适合小规模数据的排序。接下来介绍的两种时间复杂度为O($nlogn$)的算法：归并排序和快速排序。这两种算法适合大规模的数据排序。归并排序和快速排序都用到了分治思想。可以借鉴这个思想，来解决非排序的问题，比如如何在O(n)的时间复杂度内查找一个无序数组中的第K大元素？

归并排序

如果要排序一个数组，我们先把数组从中间分为前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样数组就有序了。

归并排序使用的是分治思想，即将一个大问题分解成小的子问题解决。

需要注意的是，分治是一种解决问题的处理问题，递归是一种编程技巧。

结论：

①归并排序是一种稳定的排序算法 ②归并排序的时间复杂度是O(nlogn) ③其空间复杂度是O(n)，因此不是原地排序算法

#归并排序 def merge(l1,l2,l): i,j = 0,0 while(i+j<len(l)): if j==len(l2) or (i<len(l1) and l1[i]<l2[j]): l[i+j] = l1[i] i += 1 else: l[i+j] = l2[j] j += 1 def merge_sort(l): n = len(l) if n<2: return l mid = n//2 l1 = l[0:mid] l2 = l[mid:n] merge_sort(l1) merge_sort(l2) merge(l1,l2,l) if __name__ == '__main__': l = [4,7,6,8,3,2,8,7,2,4,1,0] merge_sort(l) print(l)

快速排序

快速排序利用的也是分治思想，它的思想是：如果要排序数组中从下标从p到r之间的一组数据。我们选择从p到r之间任意一个数据作为pivot（分区点）。遍历p到r之间的数据，将小于pivot的放在左边，大于pivot的放在右边，将pivot放中间，如下图：

根据分治，递归的处理思想，我们可以用递归排序下标从q+1到r之间的数据，直到区间缩小到1，就说明所有数据都有序。

如果我们希望快排是原地排序算法，那它的空间复杂度是O(1)。有点类似于选择排序，通过游标i把A[p…r-1]分为两部分。A[p…r-1]的元素都是小于pivot，暂且叫它“已处理区间”，A[i…r-1]是“未处理区间”。每次从未处理区间A[i…r-1]中取一个元素A[j]，与pivot对比，如果小于pivot，则将其加入到已处理区间的尾部，也就是A[i]的位置，具体如下图：

插入操作需要搬移数据，耗时。采用交换可以在O(1)的时间复杂度内完成插入操作，且快排是一种原地，不稳定的排序算法。

def partition(arr,low,high): i = ( low-1 ) # 最小元素索引 pivot = arr[high] for j in range(low , high): # 当前元素小于或等于 pivot if arr[j] <= pivot: i = i+1 arr[i],arr[j] = arr[j],arr[i] arr[i+1],arr[high] = arr[high],arr[i+1] return ( i+1 ) # arr[] --> 排序数组 # low --> 起始索引 # high --> 结束索引 # 快速排序函数 def quickSort(arr,low,high): if low < high: pi = partition(arr,low,high) quickSort(arr, low, pi-1) quickSort(arr, pi+1, high) arr = [10,7,8,9,1,5,7,2,5,10,10] n = len(arr) quickSort(arr,0,n-1) print(arr)

学完了这两种时间复杂度为O(nlogn)的算法，对它们进行比较：

可以看出，归并排序的处理过程是由下到上的，先处理子问题，然后再合并。快排是从上到下，先分区，再处理问题。归并排序虽然稳定，但其为非原地排序算法。快速排序通过设计巧妙的原地分区函数，实现原地排序，解决了归并排序占用太多内存的问题。

接下来介绍三种复杂度为O(n)的排序算法：桶排序、计数排序、基数排序。因为排序算法的时间复杂度是线性的，故叫其线性排序。

桶排序

桶排序的核心思想是将要排序的数据分到几个有序的桶量，每个桶里的数据再单独进行排序。桶内排完序后，再把每个桶里的数据按顺序取出，组成的序列就是有序的。如下图：

计算桶排序的时间复杂度：假设要排序的数据有n个，将其均匀划分到m个桶内，每个桶就有k=n/m个元素。每个桶内进行快速排序，时间复杂度为O($k\ast logk$)。m个桶排序的时间复杂度就是O($m\ast k\ast logk$)。因为k=n/m。故整个时间复杂度为O($n\ast log(n/m)$)。当桶个数m接近于n时，log(n/m)是一个非常小的常量。此时桶排序时间复杂度接近于O(n)。

但实际上，桶排序对要排序数据的要求是非常苛刻的。

① 要排序的数据需要很容易就划分成m个桶，并且桶与桶之间有着天然大小顺序。

② 数据再各个桶之间分布均匀。

**桶排序比较适合用在外部排序。**桶排序速度特别快，但特别耗资源，且只能排序大于0的整数。

#桶排序，大小为1的桶 def bucket(l): s = [] ll = [0]*(max(l)+1) for num in l: ll[num]+=1 for i in range(len(ll)): for j in range(ll[i]): s.append(i) return s bucket([3,9,3,1,7,1,2,4,5,12]) #桶排序,大小为5的桶 def bucket(l): i = 5 t = int((max(l)+1)/i)+1 ll = [[] for j in range(t)] s = [] for num in l: ll[int(num/i)].append(num) for j in range(t): quickSort(ll[j],0,len(ll[j])-1) for j in range(t): s.extend(ll[j]) return s bucket([3,9,3,1,7,1,2,4,5,12,13])

计数排序

计数排序是桶排序的一种特殊情况，以A[8] = [2,5,3,0,2,3,0,3]为例，数值从0到5，故使用大小为6的数组C[6]表示桶，得到C[6]=[2,0,2,3,0,1]，再对C[6]进行顺序求和，C[6]=[2,2,4,7,7,8]。然后将A[8]倒着扫描，扫描到3时，可以从数组C中取出下标为3的值7，即到目前为止，包括自己在内，小于等于3的值有7个（也就是数组R中下标为6的位置）。当3放入R中后，小于等于3的元素只剩6个了，所以相应的C[3]要减1，变成6。以此类推…

然而计数排序只能用在数据范围不大的场景内，如果数据范围k比要排序的数据n大很多，就不适合计数排序，且计数排序只能给非负整数排序，如果要排序的数据是其他类型，要将其在不改变相对大小的情况下转化为非负整数。

#计数排序 def judge(n,l): t = 0 for i in l: if i<=n: t+=1 return t def cal_num(l): t,u = max(l),len(l) s = [0]*(t+1) r = [0]*(t+1) p = [[] for j in range(u)] o = [] for num in l: s[num]+=1 for i in range(1,t+2): r[i-1] = sum(s[0:i]) for i in l[::-1]: q = judge(i,l) p[r[i]-1].append(l[-1]) del l[-1] r[i]-=1 s[i]-=1 for i in range(u): o.append(p[i][0]) return o cal_num([2,5,3,0,2,3,0,8,3,1,11,10,3])

基数排序

假设有10万个手机号，若使用快排，时间复杂度为O($nlogn$)。若使用桶排序或计数排序，则范围过大，因此引入了基数排序。基数排序先从最后一位开始排序，然后是倒数第二位…以此类推，直到所有数字都有序，其中排序算法必须是稳定的。

如果排序的数据有k位，其中每一位都采用桶排序或计数排序，则总的时间复杂度为O($k\ast n$)=O(n)。

#基数排序 def radix_sort(l): i = 0 max_num = max(l) t = len(str(max_num)) while(i<t): s = [[] for j in range(10)] for x in l: s[int(x/(10**i))%10].append(x) print(s) l.clear() for x in s: for y in x: l.append(y) i+=1 return l

对上述八种排序算法做一个总结：

时间复杂度是否为稳定排序是否为原地排序冒泡排序O($n^2$)√√插入排序O($n^2$)√√选择排序O($n^2$)×√快速排序O($nlogn$)×√归并排序O($nlogn$)√×计数排序O(n+k) k是数据范围√×桶排序O(n)√×基数排序O(dn) d是维度√×

线性排序算法时间复杂度比较低，适用场景比较特殊，如果要写一个通用的排序函数，不能选择线性排序。如果对小规模数据进行排序，可以选择时间复杂度为O($n^2$)的算法；如果对大规模数据进行排序，时间复杂度是O($nlogn$)的算法更加高效。所以为了兼顾任意规模数据的排序，一般会首选O($nlogn$)的排序算法。但需要注意的是我们很少使用归并排序，因其空间复杂度过大。

优化快速排序

快速排序最坏时间复杂度为O($n^2$)，出现这种情况的原因是分区点选的不够合理。最理想的分区点是：被分区点分开的两个分区中，数据数量差不多。接下来介绍两种常用的分区方法：

一、三数取中法 从区间的首尾中各取一个数进行对比，取这三个数的中间值作为分区点。但是，如果要排序的数组比较大，那“三数取中”可能就不够了，可能要“五数取中”或者“十数取中”。 二、随机法 随机法就是每次从要排序的区间中，随机选择一个元素作为分区点。这种方法并不能保证每次分区点都选的比较好。从概率来看，不大可能每次分区都选的很差，因此出现O($n^2$)的可能性不大。

参考资料：王争《数据结构与算法之美》