[toc]

快速排序

快速排序 ( 英语: Quicksort ), 又称划分交换排序 ( partition-exchange sort ), 通过一趟排序, 将要排序的数据分割成独立的两部分, 其中一部分的所有数据都比另外一部分的所有数据都要小, 然后再按此方法对这两部分数据分别进行快速排序, 整个排序过程可以递归进行, 以达到整个数据变成有序序列.

步骤为:

1. 从数列中挑出一个元素, 称为 "基准" ( pivot ),

2. 重新排序数列, 所有元素比基准值小的摆放在基准前面, 所有元素比基准值大的摆在基准的后面 ( 相同的数可以到任一边 ). 在这个分区结束之后, 该基准就处于数列的中间位置. 这个称为分区 ( partition ) 操作.

3. 递归地 ( recursive ) 把小于基准值元素的子数列和大于基准值元素的子数列排序.

递归的最底部情形, 是数列的大小是零或一, 也就是永远都已经被排序好了. 虽然一直递归下去, 但是这个算法总会结束, 因为在每次的迭代 ( iteration ) 中, 它至少会把一个元素摆到它最后的位置去.

快速排序的分析

代码实现:

测试代码:

执行结果:

时间复杂度:

最优时间复杂度: O(nlogn)

最坏时间复杂度: O(n^2)

稳定性: 不稳定

从一开始, 快速排序平均需要花费 O(nlogn) 时间的描述并不明显. 但是不难观察到的是区分运算, 数组的元素都会在每次循环中走访过一次, 使用 O(n) 的时间. 在使用结合 ( concatenation ) 的版本中, 这项运算也是 O(n).

在最好的情况, 每次我们运行一次区分, 我们会把一个数列分为两个几近相等的片段. 这个意思是每次递归调用处理一半大小的数列. 因此, 在到达大小为一的数列前, 我们只要做 logn 次嵌套的调用. 这个意思就是调用树的深度是 O(logn). 但是在同一层次结构的两个程序调用中, 不会处理到原来数列的相同部分. 因此, 程序调用每一层次结构总共全部仅需要 O(n) 的时间 ( 每个调用有某些共同的额外耗费, 但是因为在每一层次结构仅仅只有 O(n) 个调用, 这些被归纳在 O(n) 系数中 ). 结果是这个算法仅需使用 O(nlogn) 时间. 

快速排序演示:

文章来源: iamarookie.blog.csdn.net，作者：我是小白呀，版权归原作者所有，如需转载，请联系作者。

原文链接：iamarookie.blog.csdn.net/article/details/109302181