1.排序算法分类
1.1 比较排序：交换排序：基础冒泡排序、优化冒泡排序、基础快速排序、递归版优化快速排序、循环版优化快速排序插入排序：基础插入排序、希尔优化插入排序选择排序：选择排序、二叉堆排序、多叉堆排序归并排序：归并排序
1.2
非比较排序：计数排序桶排序基数排序
2.基础概念解读
2.1 时间复杂度随着排序数据总量n的变大，排序总耗时的上升情况。有五个符号来表示不同的意思：
O(n^2)
大O 表示该排序算法增量情况<= n^2
o(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)
fori=1toA.length-1
forj=A.lengthdown toi
+ 1
if
A[j]
< A[j-1]
exchange A[j]
with A[j-1]
5.2 优化冒泡排序
OptimizeBubbleSort(A)
fori=1 toA.length-1
didSwap=false;
forj=A.lengthdowntoi+1
if
A[j] < A[j-1]
exchange A[j]with
A[j-1]
didExchange=true
ifdidExchange==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]
returni
+ 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)
whilestack.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
ifA[j] <= x
i=i+1
exchange A[i]withA[j]
exchange A[i+1] with
A[end]
return
i+1
5.6 基础插入排序
InsertionSort(A)
for
j=2toA.length
key = A[j]
i
= j - 1
whilei
> 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
forj = increment toA.length
key= A[j]
i= j - increment
while 0<=iandA[i] >key
A[i+increment] = A[i]
i=i- increment
A[i+increment] =key
}while(1< increment);
5.8 选择排序
SelectionSort(A)
fori=1
to n-1
min =i
for
j=i+1to n
if
A[min]
> A[j]
min = j
exchange A[min]
with A[i]
5.9 二叉堆排序
HeapSort(A)
BuildMaxHeap(A)
for i=A.lengthdownto2
exchangeA[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/2downto1
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
ifr <=A.heap-size
and A[r]
> A[largest]
largest = r
iflargest !=i
exchange A[i]
with A[largest]
MaxHeapify(A, largest)
LEFT(i)
return2i
RIGHT(i)
return2i+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
= 1to n1
L[i]=A[p +i- 1]
for
j = 1to n2
R[j]=A[q
+ j]
L[n1+1]
= 正无穷大
R[n2+1]
= 正无穷大
i
= 1
j =1
for
k = pto 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)
letC[0...k]
be anew array
for i
= 0to k
C[i]
= 0
for
j = 1toA.length
C[A[j]]
= C[A[j]]
+ 1
for i
= 1to k
C[i]
= C[i]
+ C[i-1]
forj =A.lengthdownto1
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
letB[0..
n-1]
be anew array
for i
= 0
to n-1
make B[i]an empty list
for i
= 1to n
insert A[i]
into list B[]
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
