摘要:
此文介绍了快速排序的算法以及基本分析,最后总结。
此系列文均为方便日后重复粗略查看时不必翻看书籍。
简要介绍
快速排序通过划分数组为分别大于和小于key的两个连续部分,进而递归实现排序。它的特点包括:
1. 就地排序(in place): 不需要更多的内存空间
2. 递归调用:思路简单
运行时间:
1. 最坏情况,
2. 平均情况 ,而且隐含的常数因子很小。 (何谓隐含的常数因子?…, TO BE IDTENDIFIED)
算法过程
Quick Sort过程 ([2],P85)QUICKSORT(A, p, r)
1 if p < r
2 then q ← PARTITION(A, p, r)
3 QUICKSORT(A, p, q - 1)
4 QUICKSORT(A, q + 1, r)
Quick Sort中用到的PARTITION过程 ([2],P85)
PARTITION(A, p, r)
1 x ← A[r]
2 i ← p - 1
3 for j ← p to r - 1
4 do if A[j] ≤ x
5 then i ← i + 1
6 exchange A[i] ↔ A[j]
7 exchange A[i + 1] ↔ A[r]
8 return i + 1
14 then A[k] ← L[i]
15 i ← i + 1
16 else A[k] ← R[j]
17 j ← j + 1
下图([2] 图7-2)非常好的描述了PARTITION过程中数组元素的位置分布情况。
算法分析
TODO总结
TODO。参考文献:
[1]. 算法分析导论 Section1.4平均情形分析,1.5例:快速排序的分析[2]. 算法导论,CH,V2, Chapter 7 快速排序
最新评论