排序算法实现-快速排序(Java版本)

快速排序（Quicksort），又称划分交换排序（partition-exchange sort），一种排序算法。在平均状况下，排序n个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n)算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

• 算法描述

快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。步骤为：

1. 从数列中挑出一个元素，称为"基准"（pivot），

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

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

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

其伪代码如下：

其大致排序图如下：

• 相关排序算法比较
  

1. 快速排序是二叉查找树（二叉查找树）的一个空间最优化版本。不是循序地把数据项插入到一个明确的树中，而是由快速排序组织这些数据项到一个由递归调用所隐含的树中。这两个算法完全地产生相同的比较次数，但是顺序不同。对于排序算法的稳定性指标，原地分区版本的快速排序算法是不稳定的。其他变种是可以通过牺牲性能和空间来维护稳定性的。

2. 快速排序的最直接竞争者是堆排序（Heapsort）。堆排序通常比快速排序稍微慢，但是最坏情况的运行时间总是O(n log n)。快速排序是经常比较快，除了introsort变化版本外，仍然有最坏情况性能的机会。如果事先知道堆排序将会是需要使用的，那么直接地使用堆排序比等待introsort再切换到它还要快。堆排序也拥有重要的特点，仅使用固定额外的空间（堆排序是原地排序），而即使是最佳的快速排序变化版本也需要Θ(log n)的空间。然而，堆排序需要有效率的随机存取才能变成可行。

3. 快速排序也与归并排序（Mergesort）竞争，这是另外一种递归排序算法，但有坏情况O(n log n)运行时间的优势。不像快速排序或堆排序，归并排序是一个稳定排序，且可以轻易地被采用在链表（linked list）和存储在慢速访问媒体上像是磁盘存储或网络连接存储的非常巨大数列。尽管快速排序可以被重新改写使用在炼串列上，但是它通常会因为无法随机存取而导致差的基准选择。归并排序的主要缺点，是在最佳情况下需要Ω(n)额外的空间。
   

• Java实现与分析
  

首先创建一个方法，用于快速排序某一个数列

其中调用了一个其他方法，用于排序指定序号范围内的数列，其实现如下：

其中的分区算法大致流程为：

1. 设置一个主元(待比较的数)，然后将数列分成左右两部分，并保证该主元左边的数都比该值下，右边的数都比它大

2. 循环左右两边的数列，继续执行步骤1

一次区分的样例如下：

其中最后一个数为主元，空格区分开的为左右两个序列。其实现如下：

需要注意的是在执行完这个操作后，需要把主元放到合适的位置

当分别对左右区间做排序后，最终的数列就是排序好的。

• 其他变种

1. 随机化快排：快速排序的最坏情况基于每次划分对主元的选择，而这种随机化，其实就是随机选取主元

2. 平衡快排：每次尽可能地选择一个能够代表中值的元素作为关键数据，然后遵循普通快排的原则进行比较、替换和递归。

3. 外部快排：与普通快排不同的是，关键数据是一段buffer，详细请查询其他文档。

4. 三路基数快排：结合了基数排序（radix sort，如一般的字符串比较排序就是基数排序）和快排的特点，是字符串排序中比较高效的算法。

• 性能分析
  

快速度排序基本上是外界比较流程的排序算法，基本上比其他的算法有一些优势。

其复杂度如下：

完整代码可参考: https://zhuanlan.zhihu.com/p/25658268

如果这对你有用，粉我吧，每天都有干货哦