快速排序算法的C++实现

快速排序算法的C++实现2015-05-05快速排序基本特性

时间复杂度：O（n*lgn）

最坏：O（n^2）

空间复杂度：最好情况下：O（lgn），最坏情况：O（n），平均情况：O（lgn）

不稳定。

关于快速排序的空间复杂度，谢谢@命运他爹同学指正。详述一下。

快速排序由于每次递归的时候会占用一个空间返回中间数位置，所以一次递归的空间复杂度为O（1）。

最好情况和最坏情况下的递归深度为O（lgn），相应的空间复杂度就是O（lgn）

最坏情况下的递归深度为O（n），空间复杂度为O（n）。

算法

QUICKSORT（A, p, r）if p < r then q ← PARTITION（A, p, r） //关键QUICKSORT（A, p, q - 1）QUICKSORT（A, q + 1, r） PARTITION（A, p, r）x ← A[r]i ← p - 1for j ← p to r - 1 do if A[j] ≤ x then i ← i + 1 exchange A[i] <-> A[j]exchange A[i + 1] <-> A[r]return i + 1

示例

待排序数组：7 3 5 9 8 5 1 10 4 6

一趟排序过程分析：