前言
本文用Python实现列几种排序算法（冒泡排序、选择排序、插入排序、二分插入排序、快速排序、优化快速排序，并比较了他们在随机数组上的排序效率。
本文并不会详细讲解每种排序算法的原理。
性质汇总
| 算法 | 最好 | 最坏 | 平均 | 空间 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | $O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | $\checkmark$ |
| 选择排序 | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | $\times$ |
| 插入排序 | $O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | $\checkmark$ |
| 折半插入排序 | $O(n\log n)$ | $O(n\log n)$ | $O(n\log n)$ | $O(1)$ | $\checkmark$ |
| 快速排序 | $O(n\log n)$ | $O(n^2)$ | $O(n\log n)$ | $O(\log n)$~$O(n)$ | $\times$ |
代码实现
- 本次几个算法均没有返回值，直接对原数组进行操作。
冒泡排序
from time import time
import numpy as np
def timer(fc):
def f(x):
before = time()
fc(x)
print("time: ",time()-before)
return f
# 冒泡排序
@timer
def bubble_sort(ls):
# assert type(ls) == list, "参数类型不为List"
j = len(ls)-1
while j>0:
flag = True # 如果某一次遍历过程没有发生元素交换，则已经有序，后续不需要再执行了
for i in range(j):
if ls[i]>ls[i+1]:
flag = False
ls[i], ls[i+1] = ls[i+1], ls[i]
if flag:return
j-=11-9行，实现了一个装饰器，用来给算法计时。
11-23行，实现了一个冒泡排序算法，并稍微做了一点优化，一旦每一轮遍历没有改变元素顺序，则表示数组已经有序，后续的循环不需要再执行了。
选择排序
# 选择排序
@timer
def choose_sort(ls):
for i in range(len(ls)):
tmp = ls[i]
pos = i
for j in range(i+1, len(ls)):
if ls[j]<tmp:
pos = j
tmp = ls[j]
if i!=pos:
ls[i], ls[pos] = ls[pos], ls[i]选择排序的思路也很简单，虽然时间复杂度和冒泡排序一样为$O（n^2）$,但是随机情况下，速度大约比冒泡快一倍。
插入排序
# 插入排序，在近似有序的数组上表现最优
@timer
def insert_sort(ls):
for i in range(1, len(ls)):
if ls[i]<ls[i-1]:
tmp = ls[i]
j = i-1
while j>=0 and tmp < ls[j]:
ls[j+1] = ls[j]
j-=1
ls[j+1] = tmp插入排序类似于人打扑克牌时对牌进行的排序。速度上比冒泡略快，比选择排序略慢。
在近似有序的数组上，插入排序的表现是最好的。
折半插入排序
# 二分插入排序
@timer
def binary_insert_sort(ls):
for i in range(1, len(ls)):
tmp = ls[i]
low = 0
high = i-1
while low <= high:
middle = int((low + high) / 2)
if tmp > ls[middle]:
low = middle+1
else:
high = middle-1
for j in range(i, low, -1):
ls[j] = ls[j-1]
ls[low] = tmp折半插入排序也叫二分插入排序，使用二分法来寻找插入的位置。在随机情况和最差情况下，表现比普通插入排序好得多，但在近似有序的数组上，表现不如普通插入排序。
快速排序
# 快速排序, 为了使用装饰器，多做了一层封装
@timer
def quick_sort(ls):
def partition(low, high):
pos = low
tmp = ls[low]
for i in range(low+1, high+1):
if ls[i] < tmp:
pos+=1
if pos!=i:
ls[pos], ls[i] = ls[i], ls[pos]
ls[pos], ls[low] = ls[low], ls[pos]
return pos
def sort(left, right):
if left < right:
pos = partition(left, right)
sort(left, pos-1)
sort(pos+1,right)
sort(0, len(ls)-1)快速排序无愧于它的名字，数据量大的时候效率很高，在大多数计算机上，快速排序表现得都比其他几个排序方法要好。
但是，我们也得清楚快速排序的缺点。
- 快速排序是一个递归算法，需要借助递归栈存储每一层递归调用的指针和参数。所以需要$O(logn)$—$O(n)$ 的空间复杂度。
- 快速排序的趟数取决于的递归树的深度。倘若每次快排都可以把数组划分为2个大小相同的数组，递归树的深度可以达到最小$O(logn)$，而对于有序数组，递归树退化为单枝树，递归树的深度达到 $O(n)$，排序时速度退化到简单排序的水平。不仅需要大量的存储空间，还会有“爆栈”的风险。
- 数据量小的时候，不适用与快速排序，可以选插入排序。研究表明，数组长度为5—25的时候，使用插入排序要比快速排序至少快10%。
优化后的快速排序
# 插入排序优化后的快速排序，解决快排在小数据量的排序效率低下问题
@timer
def quick_sort_insert(ls):
# 插入排序
def insert_sort(low, high):
for i in range(low+1, high):
if ls[i] < ls[i-1]:
tmp = ls[i]
j = i-1
while j>=0 and tmp < ls[j]:
ls[j+1] = ls[j]
j-=1
ls[j+1] = tmp
def partition(low, high):
pos = low
tmp = ls[low]
for i in range(low+1, high+1):
if ls[i] < tmp:
pos+=1
if pos!=i:
ls[pos], ls[i] = ls[i], ls[pos]
ls[pos], ls[low] = ls[low], ls[pos]
return pos
def sort(left, right):
if left < right-20:
pos = partition(left, right)
sort(left, pos-1)
sort(pos+1,right)
else:
insert_sort(left, right+1)
sort(0, len(ls)-1)当数组或者子数组的长度在20以下，使用直接插入排序代替快速排序。另外，我们也可以从数组中随机选择一个数作为基准，而不是总是使用数组的第一个元素作为基准，这样可以避免在近似有序情况下，快速排序的退化问题。
性能比较
测试方法，随机生成一个长度为1W的数组
# 利用numpy，从0到5W生成一个长度1W的数组
ls = np.random.randint(0,50000,10000)比较上述几种排序方法的运行时间：
冒泡排序：31.1s
选择排序：15.5s
插入排序：22.6s
折半插入排序：11.8s
快速排序：0.221s
插入排序优化后的快速排序：0.177s
By the way, python自带的list.sort()也是原地排序，对上述数组的排序时间为：0.000996s,比优化后的快速排序还要快百倍，这么快也有可能是因为这个内置方法是用C语言写出来的。
list.sort()使用的排序方法为Timsort算法，速度非常快，缺点是空间复杂度为 $O(n)$ ，比较耗费内存。
