快速排序算法

Question

如题所述

Answer 1

快速排序算法是对冒泡排序的一种改进，由东尼·霍尔在1960年提出。

快速排序是指通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序。整个排序过程可以递归进行，以此达到整个数据变成有序序列。

重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面。在这个分区结束之后，该基准就处于数列的中间位置，这个称为分区操作。递归地把小于基准值元素的子数列和大于基准值元素的子数列排序，递归到最底部时，数列的大小是零或一，也就是已经排序好了。

快速排序

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

快速排序是经常比较快，除了introsort变化版本外，仍然有最坏情况性能的机会。如果事先知道堆排序将会是需要使用的，那么直接地使用堆排序比等待introsort再切换到它还要快。堆排序也拥有重要的特点，仅使用固定额外的空间，而即使是最佳的快速排序变化版本也需要的空间。