基本概念
快速排序(Quicksort)是对冒泡排序算法的一种改进。
性质
内部排序
快速排序是一种内部排序方法。也就是说快速排序的排序对象是读入内存的数据。
比较排序
快速排序确定元素位置的方法基于元素之间关键字大小的比较。
所有基于比较方法的排序方法的时间下界不会低于O(nlgn)。这个结论的具体证明,请参考有关算法的书籍,例如《算法导论》第8章。
快速排序在理想情况下,能严格地达到O(nlgn)的下界。一般情况下,快速排序与随机化快速排序的平均情况性能都达到了O(nlgn)。
不稳定性
快速排序是一种不稳定的排序方法。简单地说,元素a1,a2的关键字有a1.key=a2.key,则不稳定的排序方法不能保证a1,a2在排序后维持原来的位置先后关系。
原地排序
在排序的具体操作过程中,除去程序运行实现的空间消费(例如递归栈),快速排序算法只需消耗确定数量的空间(即S(1),常数级空间)。
这个性质的意义,在于在内存空间受到限制的系统(例如MCU)中,快速排序也能够很好地工作。
时空复杂度
快速排序每次将待排序数组分为两个部分,在理想状况下,每一次都将待排序数组划分成等长两个部分,则需要logn次划分。而在最坏情况下,即数组已经有序或大致有序的情况下,每次划分只能减少一个元素,快速排序将不幸退化为冒泡排序,所以快速排序时间复杂度下界为O(nlogn),最坏情况为O(n^2)。在实际应用中,快速排序的平均时间复杂度为O(nlogn)。快速排序在对序列的操作过程中只需花费常数级的空间。空间复杂度S(1)。但需要注意递归栈上需要花费最少logn最多n的空间。
随机化算法
快速排序的最坏情况基于每次划分对主元的选择。基本的快速排序选取第一个元素作为主元。这样在数组已经有序的情况下,每次划分将得到最坏的结果。一种比较常见的优化方法是随机化算法,即随机选取一个元素作为主元。这种情况下虽然最坏情况仍然是O(n^2),但最坏情况不再依赖于输入数据,而是由于随机函数取值不佳。实际上,随机化快速排序得到理论最坏情况的可能性仅为1/(2^n)。所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn)的期望时间复杂度。一位前辈做出了一个精辟的总结:“随机化快速排序可以满足一个人一辈子的人品需求。”
随机化快速排序的唯一缺点在于,一旦输入数据中有很多的相同数据,随机化的效果将直接减弱。对于极限情况,即对于n个同的数排序,随机化快速排序的时间复杂度将毫无疑问的降低到O(n^2)。
算法基本思想
快速排序的基本思想是基于分治策略的。对于输入的子序列L【p..r】,如果规模足够小则直接进行排序(比如用前述的冒泡、选择、插入排序均可),否则分三步处理:
分解(Divide):将待排序列L【p..r】划分为两个非空子序列L【p..q】和L【q 1..r】,使L【p..q】中任一元素的值不大于L【q 1..r】中任一元素的值。具体可通过这样的途径实现:在序列L【p..r】中选择数据元素L【q】,经比较和移动后,L【q】将处于L【p..r】中间的适当位置,使得数据元素L【q】的值小于L【q 1..r】中任一元素的值。
递归求解(Conquer):通过递归调用快速排序算法,分别对L【p..q】和L【q 1..r】进行排序。合并(Merge):由于对分解出的两个子序列的排序是就地进行的,所以在L【p..q】和L【q 1..r】都排好序后不需要执行任何计算L【p..r】就已排好序,即自然合并。这个解决流程是符合分治法的基本步骤的。因此,快速排序法是分治法的经典应用实例之一。
区别
快速排序法是对冒泡排序法的一种改进,也是基于交换排序的一种算法。因此,被称为"分区交换排序"。在待排序序列中按某种方法选取一个元素K,以它为分界点,用交换的方法将序列分为两个部分:比该值小的放在左边,否则在右边。形成"{左子序列}K{右子序列}"。再分别对左、右两部分实施上述分解过程,直到各子序列长度为1,即有序为止。分界点元素值K的选取方法不同,将构成不同的排序法,也将影响排序的效率:例如,可取左边第1个元素为分界点、取中点A【(left right)/2】为分界点、或选取最大和最小值的平均值为分界点等。