摘要:
此文介绍了快速排序的算法以及基本分析,最后总结。
此系列文均为方便日后重复粗略查看时不必翻看书籍。
简要介绍
快速排序通过划分数组为分别大于和小于key的两个连续部分,进而递归实现排序。它的特点包括:
1. 就地排序(in place): 不需要更多的内存空间
2. 递归调用:思路简单
运行时间:
1. 最坏情况
![clip_image002[14]快速排序算法,算法-排序-快速排序(MergeSort)分析](/Files/20114/0802bf6f-7bb0-40d7-a476-fa5d38bfc4f8.gif)
2. 平均情况
![clip_image004[4]clip_image002[14]快速排序算法,算法-排序-快速排序(MergeSort)分析](/Files/20114/081c4e6c-0f5f-444d-86ae-029f838a06a7.gif)
算法过程
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
![clip_image006[5]clip_image004[4]clip_image002[14]快速排序算法,算法-排序-快速排序(MergeSort)分析](/Files/20114/5a81168a-fb62-40d0-9d72-1d0f37353f4b.gif)
下图([2] 图7-2)非常好的描述了PARTITION过程中数组元素的位置分布情况。
![clip_image007[5]clip_image006[5]clip_image004[4]clip_image002[14]快速排序算法,算法-排序-快速排序(MergeSort)分析](/Files/20114/a42edd6b-fd82-45bc-81c6-7177a362a28d.gif)
算法分析
TODO总结
TODO。参考文献:
[1]. 算法分析导论 Section1.4平均情形分析,1.5例:快速排序的分析[2]. 算法导论,CH,V2, Chapter 7 快速排序
最新评论