快速排序算法,算法-排序-快速排序(MergeSort)分析

题目：算法-排序-快速排序(MergeSort)分析
摘要：
此文介绍了快速排序的算法以及基本分析，最后总结。
此系列文均为方便日后重复粗略查看时不必翻看书籍。

简要介绍

快速排序通过划分数组为分别大于和小于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 快速排序

延伸阅读

• 2011-5-19-- php快速排序,放出一个php快速排序的c扩展
• 2011-5-24-- 常见排序算法,常见排序算法小结
• 2011-4-7-- 快速排序算法,排序算法(一)——快速排序
• 2011-4-26-- 直接排序算法,javascript算法学习（直接插入排序）
• 2011-4-19-- 快速排序,《算法导论》学习总结 — 6.第七章 快速排序
• 2010-11-24-- 快速排序算法,支招 经典算法-快速排序算法
• 2011-4-27-- 数据结构快速排序,《大话数据结构》第9章 排序 9.9 快速排序（上）
• 2008-12-10-- shell排序算法分析:C++的Shell排序算法代码学习
• 2009-10-13-- 常用排序算法:常用的内排序算法
• 2009-2-12-- 排序算法:合并排序算法