0. 评价标准
- 时间复杂度
- 空间复杂度
- 稳定性（指的是，当两个元素的Key相等时，排序之前前面的元素，在排序之后仍然出现在前面）
| 排序方法 | 原理 | 最好时间 | 平均时间 | 最坏时间 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|---|
| 冒泡排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 | |
| 直接插入法 | 把元素逐一与已经排序的数据做比较，然后插入到合适位置 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 |
| 希尔排序 | O(n^1.333) | O(1) | 不稳定 | |||
| 直接选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 | |
| 快速排序 | O(nlogn) | O(nlogn) | O(n^2) | O(logn) | 不稳定 | |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 | |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 | |
| 基数排序（链式队列） | O(mn) | O(mn) | O(mn) | O(n) | 稳定 | |
| 基数排序（顺序队列） | O(mn) | O(mn) | O(mn) | O(mn) | 稳定 |
0.1 测试数据
我们把排序的对象抽象成 DataType 数据类型，之后会使用key作为排序的目标
class DataType:
def __init__(self, key, value):
self.key = key
self.value = value
def __repr__(self):
return 'key:{key},value:{value}'.format(key=self.key, value=self.value)
data = [DataType(64, 'data1'), DataType(5, 'data2'), DataType(7, 'data3'), DataType(89, 'data4'),
DataType(6, 'data5'),DataType(24, 'data6'), DataType(24, 'data7')]
1. 平方级复杂度
1.1 冒泡排序
- 比较相邻的元素。如果第j个比第j+1个大，就交换它们两个；
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
- 针对所有的元素重复以上的步骤，除了最后一个；
- 重复步骤1~3，直到排序完成。
def bubble_sort1(arr):
for i in range(len(arr) - 1):
for j in range(len(arr) - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
#%% 测试正确性
import random
n = 10
arr = list(range(n))
random.shuffle(arr)
bubble_sort1(arr)
assert arr == list(range(n))
优化1:在若干次循环后，大概率已经是排序完成了，不需要把所有的循环都跑完。如果一轮循环都没变化，提前结束即可。
def bubble_sort2(arr):
for i in range(len(arr) - 1):
is_sorted = True
for j in range(len(arr) - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
is_sorted = False
if is_sorted:
break
优化2:
- 第i次循环后，最后i+1个元素一定是已经排好序的，之后不再参与变化（原始算法也有体现）。
- 但，末尾已经排好序的数量可能多于 i+1 个。这就又有优化空间了
- 方法：记录下每一轮排序后，最后一个发生元素交换的位置，这个元素之后的位置其实就是已经排好序的位置了，之后不再遍历
def bubble_sort3(arr):
last_exchange_idx_tmp, last_exchange_idx = 0, len(arr) - 1
for i in range(len(arr) - 1):
for j in range(last_exchange_idx):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
last_exchange_idx_tmp = j
last_exchange_idx = last_exchange_idx_tmp
优化3:鸡尾酒排序
- 方法：交替进行，从左到右冒泡，下一轮从右往左冒泡，下下一轮又从左往右冒泡，以此类推
- 适用场景：大多数元素已有序，但位置未必正确。例如
2,3,4,5,6,7,8,1，冒泡排序怎样都要8轮，但鸡尾酒排序只需要2轮
1.2 直接插入排序
- 从第一个元素开始，该元素可以认为已经被排序；
- 取出下一个元素，在已经排序的元素序列中从后向前扫描；
- 如果该元素（已排序）大于新元素，将该元素移到下一位置；
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
- 将新元素插入到该位置后；
- 重复步骤2~5。
def InsertSort(data):
len_data = len(data)
for i in range(len_data - 1):
tmp = data[i + 1]
j = i
while (j > -1) and (tmp.key < data[j].key):
data[j + 1] = data[j]
j -= 1
data[j + 1] = tmp
return data
- 时间复杂度
- 最好复杂度。已经完成排序的序列，比较次数n-1,赋值次数2(n-1),复杂度$O(n)$
- 最坏复杂度。原序列是反序排列，复杂度是$O(n^2)$
- 平均复杂度。原序列随机排列，复杂度是$O(n^2/4)=O(n^2)$
- 空间复杂度$O(1)$
- 稳定性：稳定
1.3 希尔排序
为了减少数据移动操作。
- 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
- 按增量序列个数k，对序列进行k 趟排序；
- 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表
- 进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
1.4 直接选择排序
思路：每次在池子中选择一个最小的，放到序列前面
- 初始状态：无序区为R[1..n]，有序区为空；
- 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
- n-1趟结束，数组有序化了。
def SelectSort(data):
len_data = len(data)
for i in range(len_data - 1):
min_index = i
for j in range(i + 1, len_data): # 找到之后最小的
if data[j].key < data[min_index].key:
min_index = j
if min_index != i: # 如果最小的还是最开始的那个，不进行交换
data[min_index], data[i] = data[i], data[min_index]
return data
2. nlogn 复杂度
2.1 快速排序
下面这个图有些问题，不是快排。
快排思路
- 找一个基准值
- 使小于基准值的放到左边，大于基准值p的放到右边
- 上面得到了2个子列，对每个子列重复1,2
那么第二步如何实现呢？
- 两个指针指向两个端点，序号分别是i,j，后面的算法两个指针向中间移动
- 把基准值p拿出来，这样链上有个空位。例如，选左端点为p，这样i就是空位
- 右指针j向左移动，如果遇到比p小的，就填到空位i上。然后j就变成空位（看成空位，实际不必替换）。
- 如果i是空位，j向左移动；如果j是空位，i向右移动
- 直到i==j，然后把p填到i上
- 完成
def quick_sort(start_idx, end_idx, arr):
if start_idx >= end_idx:
return
pivot_idx = partition(start_idx, end_idx, arr)
quick_sort(start_idx, pivot_idx - 1, arr)
quick_sort(pivot_idx + 1, end_idx, arr)
def partition(start_idx, end_idx, arr):
# 这里用最左边为pivot；也可以先随机找一个值，与第一个交换，达成随机 pivot 的目的
pivot = arr[start_idx]
left, right = start_idx, end_idx
hole = 0 # 0：代表 left 是空洞；1：代表right是空洞
while left < right:
if hole == 0:
if arr[right] < pivot:
arr[left] = arr[right]
hole = 1
left += 1
else:
right -= 1
else:
if arr[left] >= pivot:
arr[right] = arr[left]
hole = 0
right -= 1
else:
left += 1
arr[left] = pivot
return left
2.2 堆排序
# 懒省事，做个弊，代价就是不能针对第0章定义的 DataType 进行排序了
import heapq
def HeapSort(data):
heapq.heapify(data) # O(n)
res = []
while data:
res.append(heapq.heappop(data))
return res
HeapSort([[3, 9], [5, 2], [7, 9], [1, 3], [3, 5]])
4. 归并排序
- 把长度为n的输入序列分成两个长度为n/2的子序列；
- 对这两个子序列分别采用归并排序（触发递归）；
- 将两个排序好的子序列合并成一个最终的排序序列。
3. 线性复杂度
3.1 计数排序
适用情况：取值范围为有限个整数，例如，有100万个数字，它们都是 0 到 9 的整数，要求排序 算法：循环一次记数，再循环一次把数字填回去
def count_sort(arr):
counter = [0 for _ in range(max(arr) + 1)]
for val in arr:
counter[val] += 1
pointer = 0
for i in range(len(arr)):
if counter[pointer] == 0:
pointer += 1
arr[i] = pointer
counter[pointer] -= 1
import random
n = 10000
arr = [random.randint(0, 9) for i in range(n)]
count_sort(arr)
assert arr == sorted(arr)
3.2 桶排序
算法步骤
- 按照最大值最小值，创建n个桶
- 遍历arr，把元素放入桶内
- 每个桶内做排序
算法复杂度
- 最好的情况：n个元素，均匀分到n个桶内。时间复杂度 On，空间复杂度 On
- 最坏的情况：极不均匀，大多数元素被分到同一个桶内，退化为快排，时间复杂度为O(nlogn)，空间复杂度为 On（比快排浪费）
3.3. 基数排序
6. 大规模数据排序
2G内存，如何给20亿个int数据（8G）排序？
- 把8G数据分4片，每一片做排序
- 对于每片，每次读取1个值，比较后输出
- 这个题目有4片，n片的话第二步可以用堆排序
参考文献
朱战立：《数据结构-使用C语言》，西安交通大学出版社
https://www.cnblogs.com/onepixel/articles/7674659.html
