Sorting

总结排序算法,不局限于本课程所述的部分

综述

问题

假设要将一个大小为 NN 的从小到大排序。

思路

1. 每次将一个元素移动到最终位置

一些排序算法,如选择排序 (selection sort),冒泡排序 (bubble sort) 以及堆排序 (heap sort),每次将一个元素移动到最终位置,这样就能将大小为 NN 的问题转化成大小为 N1N-1 的问题。

2. 每次将每个元素放到更接近最终位置的地方

一些排序算法,如插入排序 (insertion sort),快速排序 (quick sort),计数排序 (counting sort) 以及基数排序 (radix sort),每次将每个元素放到更接近最终位置的地方,使得整体序列的逆序数量逐渐变少,并最终达到排序目的。

3. 分治

如归并排序 (merge sort)

复杂度和运行时

  • 排序至少要遍历一遍待排序列,因此排序算法的复杂度为 O(n)O(n)

  • 影响复杂度的因素包括:

    • 算法本身的流程复杂程度及启动开销:简单的算法虽然复杂度常为 O(n2)O(n^2) ,但它的其它开销(常数项)可能很小,因此面对长度较小(如 < 10)的序列常常有更快的性能。因此实际运用中,常常会通过判断序列大小来选择所使用的排序算法

    • 多余的空间,如变量及递归的栈空间

    • 缓存:算法运行过程中的大部分比较操作如果都是发生在相邻元素之间,就容易利用数据的空间分布特点,获得更高的缓存命中率以及数据预取

    • 各种类型的输入考量:乱序、已经排好序、倒着排好序、接近排好序等

  • 基于比较的排序算法对待排序列没有任何假设,理想情况下,在任何输入面前都能够做到 θ(nlogn)\theta(nlogn) 的算法复杂度,如堆排序、归并排序等。

  • 如果我们可以对数据做一些额外的假设,就可能获得比 θ(nlogn)\theta(nlogn) 更好的算法复杂度,如在计数排序中,我们假设数据分布在一定范围内。

排序算法集锦

冒泡排序(Bubble Sort)

复杂度小结

Case

Time Complexity

Space Complexity

Best

O(n)O(n)

O(1)O(1)

Worst

O(n2)O(n^2)

O(1)O(1)

Average

O(n2)O(n^2)

O(1)O(1)

思路

从左往右冒泡,每次比较左右两个元素,如果前者大于后者,则交换位置,一共循环 N1N-1 次,第 i 次循环结束时,第 i 大的元素都会移动到正确的位置上。

bubble.py
def bubble(A):
L = len(A)
for i in range(L-1):
flag = True
for j in range(L-i-1):
if A[j] > A[j+1]:
A[j], A[j+1] = A[j+1], A[j]
flag = False
if flag:
break

选择排序(Selection Sort)

复杂度小结

Case

Time Complexity

Space Complexity

All

O(n2)O(n^2)

O(1)O(1)

思路

选择排序是所有排序中最直观的排序,从左开始,每次从剩余元素中选择最大(小)的元素,放到剩余序列的最右(左)边。

selection.py
def selection(A):
L = len(A)
for i in range(L-1):
mi = 0
for j in range(1, L-i):
if A[j] > A[mi]:
mi = j
A[mi], A[L-i-1] = A[L-i-1], A[mi]

插入排序(Insertion Sort)

复杂度小结

Case

Time Complexity

Space Complexity

Best

O(n)O(n)

O(1)O(1)

Worst

O(n2)O(n^2)

O(1)O(1)

Average

O(n2)O(n^2)

O(1)O(1)

思路

插入排序与打扑克时整理牌的方法类似,从左向右开始,第 i 轮结束保证前 i 个元素已经排好序。

insertion.py
def insertion(A):
for i in range(1, len(A)):
for j in range(i, 0, -1):
if A[j] < A[j-1]:
A[j], A[j-1] = A[j-1], A[j]
else:
break

快速排序(Quick Sort)

复杂度小结

Case

Time Complexity

Space Complexity

Best

O(nlogn)O(nlogn)

O(1)O(1)

Worst

O(n2)O(n^2)

O(1)O(1)

Average

O(nlogn)O(nlogn)

O(1)O(1)

思路

有点像二分,每次选取一个 pivot,将所有小于 pivot 的数和所有大于 pivot 的数,分别作为两个子序列,递归地排序。其中 pivot 的选择决定了最终排序的复杂度。

def quicksort(A):
_quicksort(A, 0, len(A))
def _quicksort(A, l, h):
if l < h:
pi = _partition(A, l, h)
_quicksort(A, l, pi)
_quicksort(A, pi+1, h)
def _partition(A, l, h):
# 任何 pivot 选择策略都可以,这里选择最后一个
pi = h-1
# 将 pivot 交换到最后
A[pi], A[h-1] = A[h-1], A[pi]
pi, p = h-1, p[h-1]
i = l-1
for j in range(l, h-1):
if A[j] < p:
i += 1
A[i], A[j] = A[j], A[i]
i += 1
A[h-1], A[i] = A[i], A[h-1]
return i

快速排序快的原因在于:

  1. pivot 选择得好时,能够获得 θ(nlogn)\theta(nlogn) 的时间复杂度

  2. 它利用了 spatial locality,总是比较相邻的元素,因此很好地利用 cache

堆排序(Heap Sort)

复杂度小结

Case

Time Complexity

Space Complexity

All

O(nlogn)O(nlogn)

O(1)O(1)

使用堆(具体参考 Priority Queue Interface & Implementation 一节),先对原序列建堆(原地建堆可以获得 O(1)O(1) 的空间复杂度),后每次从堆中 pop 出最大值,放到序列末尾即可。

归并排序(Merge Sort)

复杂度小结

Case

Time Complexity

Space Complexity

All

O(nlogn)O(nlogn)

O(n)O(n)

思路

每次将序列二等分,各部分排好序后,再合并。

merge_recursive.py
merge_iterative.py
merge_recursive.py
def mergesort(A):
_mergesort(A, 0, len(A))
def _mergesort(A, l, h):
# 区间内只有小于 2 个元素,直接返回,无需排序
if l+1 >= h:
return
m = (l+h)//2
_mergesort(A, l, m)
_mergesort(A, m, h)
_merge(A, l, m, h)
def _merge(A, l, m, h):
tmp = []
i, j = l, m
while i < m and j < h:
if A[i] < A[j]:
tmp.append(A[i])
i += 1
elif A[i] > A[j]:
tmp.append(A[j])
j += 1
else:
tmp.append(A[i])
tmp.append(A[j])
i += 1
j += 1
while i < m:
tmp.append(A[i])
i += 1
while j < h:
tmp.append(A[j])
j += 1
A[l:h] = tmp
merge_iterative.py
def mergesort(A):
step = 1
ll = len(A)
while step <= ll:
h = 0
for h in range(0, ll, step*2):
l, m, r = h, h+step, min(ll, h+2*step)
p, q = l, m
while p < m and q < r:
if A[p] < A[q]:
p += 1
else:
tmp = A[q]
A[p+1: q+1] = A[p:q]
A[p] = tmp
p, m, q = p+1, m+1, q+1
step *= 2
return A

计数排序(Counting Sort)

复杂度小结

Case

Time Complexity

Space Complexity

All

O(n)O(n)

O(k)O(k)

其中 n 表述序列大小,k 表示元素的范围大小

思路

统计元素所处范围内中每个元素的数量,然后从小到大遍历生成新序列即可

counting.py
def counting_sort(A, k, fn=lambda ele: ele):
ll = len(A)
counting_table = [0]*k
for ele in A:
counting_table[fn(ele)] += 1
position_table = counting_table
count = ll
for i in reversed(range(len(position_table))):
count -= position_table[i]
position_table[i] = count
ret = [0]*ll
for i, ele in enumerate(A):
key = fn(ele)
ret[position_table[key]] = ele
position_table[key] = position_table[key] + 1
return ret

基数排序(Radix Sort)

复杂度小结

Case

Time Complexity

Space Complexity

All

O(d(n+k))O(d*(n+k))

O(k)O(k)

其中,d 表示最大数的位数,k 表示元素基数大小(如二进制,k = 2;十进制,k = 10)

思路

从最小的位数开始,如十进制中的个位,每轮对所有元素的该位数进行一次计数排序。

radix_sort.py
def radix_sort(A, d, k):
def ele_to_key_gen(pos):
def ele_to_key(ele):
count = d - pos - 1
while count > 0:
ele = ele // k
count -= 1
return ele % k
return ele_to_key
for pos in reversed(range(d)):
ele_to_key = ele_to_key_gen(pos)
A = counting_sort(A, k, ele_to_key)
return A

现实中的排序算法

TimSort

复杂度小结

Case

Time Complexity

Space Complexity

All

O(nlogn)O(nlogn)

O(n)O(n)

思路

当序列较小时,使用插入排序;当序列较大时,先将序列分成多组,每组先使用插入排序,后对不同组递归地使用归并排序中的归并步骤。

timsort.py
def insertion_sort(A):
for i in range(1, len(A)):
for j in range(i, 0, -1):
if A[j] < A[j-1]:
A[j], A[j-1] = A[j-1], A[j]
else:
break
return A
def merge(A, B):
li, lj = len(A), len(B)
R = []
i, j = 0, 0
while i < li and j < lj:
if A[i] < B[j]:
R.append(A[i])
i += 1
elif A[i] > B[j]:
R.append(B[j])
j += 1
else:
R.append(A[i])
R.append(B[j])
i += 1
j += 1
while i < li:
R.append(A[i])
i += 1
while j < lj:
R.append(B[j])
j += 1
return R
def timsort(A):
ll = len(A)
RUN = 32
for i in range(0, ll, RUN):
A[i:i+RUN] = insertion_sort(A[i:i+RUN])
RUNinc = RUN
while RUNinc < ll:
for i in range(0, ll, 2*RUNinc):
A[i:i+2*RUNinc] = merge(A[i:i+RUNinc],
A[i+RUNinc:i+2*RUNinc])
RUNinc *= 2
return A

外排序算法

TODO

参考 https://github.com/melvilgit/external-Merge-Sort

参考