1. 排序算法分类
1.1 比较排序：交换排序：基础冒泡排序、优化冒泡排序、基础快速排序、递归版优化快速排序、循环版优化快速排序插入排序：基础插入排序、希尔优化插入排序选择排序：选择排序、二叉堆排序、多叉堆排序归并排序：归并排序 1.2 非比较排序：计数排序桶排序基数排序
2. 基础概念解读
2.1 时间复杂度随着排序数据总量 n 的变大，排序总耗时的上升情况。有五个符号来表示不同的意思：O(n^2) 大 O 表示该排序算法增量情况 <= n^2o(n^2) 小 o 表示该排序算法增量情况 < n^2θ(n^2) 希腊字母 theta 表示该排序算法增量情况 == n^2ω(n^2) 希腊字母小欧米伽 表示该排序算法增量情况 > n^2Ω(n^2) 希腊字母大欧米伽 表示该排序算法增量情况 >= n^2
2.2 稳定性如果 a =b，排序前 a 在 b 之前，排序后 a 还在 b 之前，则稳定如果 a =b，排序前 a 在 b 之前，排序后 a 在 b 之后，则不稳定
2.3 逆序对比如 {2, 4, 3, 1} 这样一个数列，就有 {2, 1},{4, 3},{4, 1},{3, 1} 等逆序对，数量为 4
3. 排序算法对比
4. 代码实现（Java）
https://github.com/dawnchengx…
5. 伪代码实现
5.1 基础冒泡排序
BasicBubbleSort(A)
for i=1 to A.length-1
for j=A.length down to i + 1
if A[j] < A[j-1]
exchange A[j] with A[j-1]
5.2 优化冒泡排序
OptimizeBubbleSort(A)
for i=1 to A.length-1
didSwap = false;
for j=A.length down to i + 1
if A[j] < A[j-1]
exchange A[j] with A[j-1]
didExchange = true
if didExchange == true
return
5.3 基础快速排序
BasicQuickSort(A, p, r)
if p < r
q = BasicPartition(A, p, r)
BasicQuickSort(A, p, q-1)
BasicQuickSort(A, q+1, r)
BasicPartition(A, p, r)
x = A[r]
i = p-1
for j=p to r-1
if A[j] <= x
i = i + 1
exchange A[i] with A[j]
exchange A[i+1] with A[r]
return i + 1
5.4 递归优化快速排序
RecuOptimizeQuickSort(A, sort, end)
if start < end
mid = RecuOptimizePartition(A, start, end)
RecuOptimizeQuickSort(A, start, mid-1)
RecuOptimizeQuickSort(A, start+1, end)
RecuOptimizePartition(A, start, end)
生成介于 start 和 end 之间的三个不重复的随机数 r1,r2,r3
取 A[r1],A[r2],A[r3]这三个数的中位数，并将该中位数的下标赋值给 r0
x = A[r0]
i = start – 1
for j = start to end – 1
if A[j] <= x
i = i + 1
exchange A[i] with A[j]
exchange A[i+1] with A[end]
return i+1
5.5 循环优化快速排序
LoopOptimizeQuickSort(A)
stack = []
start = 0
end = A.length – 1
stack.push(start)
stack.push(end)
while stack.isNotEmpty()
end = stack.pop()
start = stack.pop()
if start < end
base = LoopOptimizePartition(A, start, end)
// 右半边
stack.push(base+1)
stack.push(end)
// 左半边
stack.push(start)
stack.push(base-1)
LoopOptimizePartition(A, start, end)
生成介于 start 和 end 之间的三个不重复的随机数 r1,r2,r3
取 A[r1],A[r2],A[r3]这三个数的中位数，并将该中位数的下标赋值给 r0
x = A[r0]
i = start – 1
for j = start to end – 1
if A[j] <= x
i = i + 1
exchange A[i] with A[j]
exchange A[i+1] with A[end]
return i+1
5.6 基础插入排序
InsertionSort(A)
for j=2 to A.length
key = A[j]
i = j – 1
while i > 0 and A[i] > key
A[i+1] = A[i]
i = i – 1
A[i+1] = key
5.7 希尔优化插入排序
ShellInsertionSort(A)
increment = A.length
do {
increment = increment/3 + 1
for j = increment to A.length
key = A[j]
i = j – increment
while 0 <= i and A[i] > key
A[i+increment] = A[i]
i = i – increment
A[i+increment] = key
}while(1 < increment);
5.8 选择排序
SelectionSort(A)
for i=1 to n-1
min = i
for j=i+1 to n
if A[min] > A[j]
min = j
exchange A[min] with A[i]
5.9 二叉堆排序
HeapSort(A)
BuildMaxHeap(A)
for i = A.length downto 2
exchange A[1] with A[i]
A.heap-size = A.heap-size – 1
MaxHeapify(A, 1)
BuildMaxHeap(A)
A.heap-size = A.length
for i = A.length/2 downto 1
MaxHeapify(A, i)
MaxHeapify(A, i)
l = LEFT(i)
r = RIGHT(i)
if l <= a.heap-size and A[l] > A[i]
largest = l
else largest = i
if r <= A.heap-size and A[r] > A[largest]
largest = r
if largest != i
exchange A[i] with A[largest]
MaxHeapify(A, largest)
LEFT(i)
return 2i
RIGHT(i)
return 2i+1
5.10 多叉堆排序 5.11 归并排序
MergeSort(A, p, r)
if p < r
q = (p+r)/2 (向下取整)
MergeSort(A, p, q)
MergeSort(A, q+1, r)
Merge(A, p, q, r)
Merge(A, p, q, r)
n1 = q – p + 1
n2 = r – q
let L[1..n1+1] and R[1..n2 + 1] be new arrays
for i = 1 to n1
L[i] = A[p + i – 1]
for j = 1 to n2
R[j] = A[q + j]
L[n1+1] = 正无穷大
R[n2+1] = 正无穷大
i = 1
j = 1
for k = p to r
if L[i] <= R[j]
A[k] = L[i]
i = i + 1
else
A[k] = R[j]
j = j + 1
5.12 计数排序
CountingSort(A, B, k)
let C[0…k] be a new array
for i = 0 to k
C[i] = 0
for j = 1 to A.length
C[A[j]] = C[A[j]] + 1
for i = 1 to k
C[i] = C[i] + C[i-1]
for j = A.length downto 1
B[C[A[j]]] = A[j]
C[A[j]] = C[A[j]] – 1
5.13 基数排序 https://www.jianshu.com/p/68b…5.14 桶排序
https://www.cnblogs.com/zer0Black/p/6169858.html
BucketSort(A)
n = A.length
let B[0.. n-1] be a new array
for i = 0 to n-1
make B[i] an empty list
for i = 1 to n
insert A[i] into list B[<nA[i]向下取整 >]
for i = 0 to n-1
sort list B[i] with insertion sort
concatenate the lists B[0],B[1],…,B[n-1] together in order