整个十一假期就在折腾这几个算法，这篇总结性文章就是简要的介绍了几个基础算法的特性，并附带了 Python 的实现。
不同算法适合不同情况的数组，但在不知道输入规律的时候，使用时间复杂度低算法的比较保险。
Big O：上界
Big Ω：下界
Big Θ：确界
Big O 比较
O(n²)：冒泡排序（稳定）/选择排序（不稳定）/插入排序（稳定）
O(nlgn)~O(n²)：希尔排序（不稳定）
O(nlgn)：堆排序（不稳定）/归并排序（稳定）/快速排序（不稳定）
Bubble Sort 冒泡排序
def bubble_sort(arry):
n = len(arry) #获得数组的长度
for i in range(n):
for j in range(1,n-i):
if arry[j-1] > arry[j] : #如果前者比后者大
arry[j-1],arry[j] = arry[j],arry[j-1] #则交换两者
return arry
时间复杂度、稳定性
平均情况：O(n²)
最坏情况：O(n²)
最好情况：O(n)
稳定
辅助空间O(1)
特点
最优情况为全部正序时经过 n-1 次比较即可完成排序，最差情况是倒序。因此冒泡算法对数组的有序性很敏感，适合对规模较小、且比较有序的数据进行排序。[1]
优化方案
- 如果某一次遍历没有发生数据交换，则代表已完成排序，可停止迭代。
- 记录遍历时最后一次数据交换的位置，后面的数据已经有序，因此可以缩小下次循环的范围。
Selection Sort 选择排序
def select_sort(ary):
n = len(ary)
for i in range(0,n):
min = i #最小元素下标标记
for j in range(i+1,n):
if ary[j] < ary[min] :
min = j #找到最小值的下标
ary[min],ary[i] = ary[i],ary[min] #交换两者
return ary
时间复杂度、稳定性
平均情况：O(n²)
最坏情况：O(n²)
最好情况：O(n²)
不稳定
辅助空间O(1)
特点
运行时间与输入状态无关（随机排列与正序排列消耗相同的时间）。同时移动次数最少（与数组大小呈线性关系）。[1]
Insertion Sort 插入排序
def insert_sort(ary):
n = len(ary)
for i in range(1,n):
if ary[i] < ary[i-1]:
temp = ary[i]
index = i #待插入的下标
for j in range(i-1,-1,-1): #从i-1 循环到 0 (包括0)
if ary[j] > temp :
ary[j+1] = ary[j]
index = j #记录待插入下标
else :
break
ary[index] = temp
return ary
时间复杂度、稳定性
平均情况：O(n²)
最坏情况：O(n²)
最好情况：O(n)
稳定
辅助空间：O(1)
特点
输入状态会影响运行效率，对有序数组排序要比对随机排列、逆序排列的数组快，因此适用于部分有序的非随机数组。当『数组中每个元素距离它的最终位置都不愿』『一个有序的大数组接一个小数组』『数组中只有几个元素的位置不正确』时，插入算法的速度很可能比其他算法都快。[2]
Shell Sort 希尔排序
def shell_sort(ary):
n = len(ary)
gap = round(n/2) #初始步长 , 用round四舍五入取整
while gap > 0 :
for i in range(gap,n): #每一列进行插入排序 , 从gap 到 n-1
temp = ary[i]
j = i
while ( j >= gap and ary[j-gap] > temp ): #插入排序
ary[j] = ary[j-gap]
j = j - gap
ary[j] = temp
gap = round(gap/2) #重新设置步长
return ary
时间复杂度、稳定性
平均情况：O(nlgn)~O(n²)
最坏情况：O(n²)
最好情况：O(n1.3)
不稳定
辅助空间：O(1)
特点
希尔排序将数组分成较短的子数组、并使之部分有序，很适合插入排序。希尔排序对中等大小数组的排序时间可以接受，代码量小，且不需要额外内存空间。当没有系统排序函数可用时，可以考虑先用希尔排序，再考虑是否值得替换为更复杂的排序算法。[3]
Merge Sort 归并排序
def merge_sort(ary):
if len(ary) <= 1 : return ary
num = int(len(ary)/2) #二分分解
left = merge_sort(ary[:num])
right = merge_sort(ary[num:])
return merge(left,right) #合并数组
def merge(left,right):
'''合并操作，
将两个有序数组left[]和right[]合并成一个大的有序数组'''
l,r = 0,0 #left与right数组的下标指针
result = []
while l<len(left) and r<len(right) :
if left[l] < right[r]:
result.append(left[l])
l += 1
else:
result.append(right[r])
r += 1
result += left[l:]
result += right[r:]
return result
时间复杂度、稳定性
平均情况：O(nlgn)
最坏情况：O(nlgn)
最好情况：O(nlgn)
稳定
辅助空间：O(n)
特点
归并排序在最坏的情况下复杂度为O(nlgn)，和其他基于比较的排序算法所需的最小比较次数相同。
Quick Sort 快速排序
用递归在 Python 中实现快速排序会遇到 RuntimeError: maximum recursion depth exceeded 的错误提示，原因是 Python 的递归深度默认为1000（可以用 sys.getrecursionlimit() 来查看），有两种方式解决为题。一种是用循环重写算法，另一种比较简单粗暴，直接用 sys.setrecursionlimit(99999) 把递归深度设置为 99999 这种大数字，更详细可参见这里。
def quick_sort(ary):
return qsort(ary,0,len(ary)-1)
def qsort(ary,left,right):
#快排函数，ary为待排序数组，left为待排序的左边界，right为右边界
if left >= right : return ary
key = ary[left] #取最左边的为基准数
lp = left #左指针
rp = right #右指针
while lp < rp :
while ary[rp] >= key and lp < rp :
rp -= 1
while ary[lp] <= key and lp < rp :
lp += 1
ary[lp],ary[rp] = ary[rp],ary[lp]
ary[left],ary[lp] = ary[lp],ary[left]
qsort(ary,left,lp-1)
qsort(ary,rp+1,right)
return ary
时间复杂度、稳定性
平均情况：O(nlgn)
最坏情况：O(n²)
最好情况：O(nlgn)
不稳定
辅助空间：O(nlgn)~O(n)
特点
在实际应用中，一般比其他算法快很多，内循环很小，原地排序（仅需要很小的辅助栈），且将长度为 N 的数组排序的时间与 NlgN 成正比。但很脆弱，实际性能会因某些错误变成平方级。[4]
快速排序和归并排序使用分治法和递归进行排序，但快排在合并子数组后是自然有序的大数组；归并在合并阶段则繁琐一些，还要再次进行比较。
在对数组进行切分不平衡时，会导致性能低效（例如第一次从最小元素切分、第二次从第二小的元素切分……）。解决该问题，可以对数组进行随机排序，避免性能下降到极低。
优化
- 快排在小数组中比插入排序慢，因此在排序小数组时使用插入排序。
- 三取样切分。
- 熵最优排序[5]
以上三种优化是《Algorithms 4th》中对于快排性能的优化，都是对算法本身做了一些改进。而最著名的优化则是《算法导论》中提到的『随机化快速排序』，与上述三种性能优化有很大不同。
随机化快速排序，一般来说都是将取主元的过程随机化。随机化快速排序的『优化』，并没有提高快排的性能，而是避免了某些序列使快排性能大幅降低到O(n²)的可能性、防止他人设计一个序列对服务器发起DoS攻击，使排序更加稳定和安全（我发现还有很多人有类似的误解）。事实上随机化快速排序和普通快速排序在时间复杂度上同为O(nlgn)，实际实验中也没有显著差异。
知乎上一个用户对快排和随机快排的性能做了测试，
但我猜他可能也理解错了，他所做的只是在优化随机快排的代码，
但并没有显著提高算法性能或降低复杂度（
知乎链接）。Thomas Cormen 在 Quora 中也回答了关于随机化快排和普通快排性能差异的问题（
Quora链接），但是他本人在《算法导论》（中文版100页，
英文版179页）中并没有把这个问题讲的很透彻，
也许算是一个微小的失误。
Heap Sort 堆排序
def heap_sort(ary) :
n = len(ary)
first = int(n/2-1) #最后一个非叶子节点
for start in range(first,-1,-1) : #构造大根堆
max_heapify(ary,start,n-1)
for end in range(n-1,0,-1): #堆排，将大根堆转换成有序数组
ary[end],ary[0] = ary[0],ary[end]
max_heapify(ary,0,end-1)
return ary
#最大堆调整：将堆的末端子节点作调整，使得子节点永远小于父节点
#start为当前需要调整最大堆的位置，end为调整边界
def max_heapify(ary,start,end):
root = start
while True :
child = root*2 +1 #调整节点的子节点
if child > end : break
if child+1 <= end and ary[child] < ary[child+1] :
child = child+1 #取较大的子节点
if ary[root] < ary[child] : #较大的子节点成为父节点
ary[root],ary[child] = ary[child],ary[root] #交换
root = child
else :
break
时间复杂度、稳定性
平均情况：O(nlgn)
最坏情况：O(nlgn)
最好情况：O(nlgn)
不稳定
辅助空间：O(1)
2. 特点
目前唯一的能最优利用时间与空间的算法，最坏情况下也能保证 2NlgN 次比较和恒定的辅助空间。当空间紧张时（例如嵌入式），堆排序用几行代码就能实现实现较好性能。
缺点是无法利用缓存，缓存未命中的次数远高于大多数在相邻元素间比较的算法。
通过倍率实验预测程序的增长数量级
可以使用倍率实验来预测任意程序的增长数量级：
每次实验时使输入翻倍，计算时间，并求两次运行时间的比值。反复运行直到比值趋近于2的b次方。[6]
算法的『稳定性』是什么
稳定性指，当排序的元素中有相同的值时，这些具有相同值的元素在排序后的前后位置是否发生变化的性质。如果变化，则不稳定；如果不变化，则稳定。在 Bubble Sort 中，相邻元素互相交换，如果两个相邻元素相等则不需交换；如果两个相等的元素彼此之间有间隔，那么即便它们和相邻元素交换后，其相对的前后位置也不会发生变化，所以是稳定的。而在 Selection Sort 中，第一个元素与最小的元素交换、第二个元素与第二小元素交换等等，间隔有可能很大从而在交换时跳过了相同值的元素，进而造成相同值元素前后位置改变，因此是不稳定的。
排序的键值有可能只是元素的一个属性，如果元素本身还具有其他属性，那么键值相同的元素排序后的相对顺序还与其他属性有关。例如用稳定的算法对员工按工资排序，假如原数组是按年龄排序的，那么月薪同为7000元的3个人在按工资排序后仍然可以保持年龄正序，即最初的相对位置不变。
参考资料：
[1]《Algorithms 4th》 P248
[2]《Algorithms 4th》 P252
[3]《Algorithms 4th》 P262
[4]《Algorithms 4th》 P288
[5]《Algorithms 4th》 P296
[6]《Algorithms 4th》 P121
Tagged : python / 快速排序 / 算法 / 算法导论 / 编程
