排序高级之交换排序_快速排序-阿里云开发者社区

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n²)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

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

步骤为：

从数列中挑出一个元素，称为 "基准"（pivot），
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

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

优化的排序算法

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

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

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

正规的分析

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

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

另外一个方法是为T(n)设立一个递归关系式，也就是需要排序大小为n的数列所需要的时间。在最好的情况下，因为一个单独的快速排序调用牵涉了O(n)的工作，加上对n/2大小之数列的两个递归调用，这个关系式可以是：

T( n) = O( n) + 2T( n/2)

解决这种关系式型态的标准数学归纳法技巧告诉我们T(n) = O(n log n)。

事实上，并不需要把数列如此精确地分区；即使如果每个基准值将元素分开为 99% 在一边和 1% 在另一边，调用的深度仍然限制在 100log n，所以全部运行时间依然是O(n log n)。

然而，在最坏的情况是，两子数列拥有大各为 1 和 n-1，且调用树（call tree）变成为一个 n 个嵌套（nested）调用的线性连串（chain）。第 i 次调用作了O(n-i)的工作量，且 $\sum_{i=0}^n (n-i) = O(n^2)$ 递归关系式为：

T( n) = O( n) + T(1) + T( n - 1) = O( n) + T( n - 1)

这与插入排序和选择排序有相同的关系式，以及它被解为T(n) = O(n²)。

乱数快速排序的期望复杂度

乱数快速排序有一个值得注意的特性，在任意输入数据的状况下，它只需要O(n log n)的期望时间。是什么让随机的基准变成一个好的选择？

假设我们排序一个数列，然后把它分为四个部份。在中央的两个部份将会包含最好的基准值；他们的每一个至少都会比25%的元素大，且至少比25%的元素小。如果我们可以一致地从这两个中央的部份选出一个元素，在到达大小为1的数列前，我们可能最多仅需要把数列分区2log₂ n次，产生一个 O(nlogn)算法。

不幸地，乱数选择只有一半的时间会从中间的部份选择。出人意外的事实是这样就已经足够好了。想像你正在翻转一枚硬币，一直翻转一直到有 k 次人头那面出现。尽管这需要很长的时间，平均来说只需要 2k 次翻动。且在 100k 次翻动中得不到 k 次人头那面的机会，是像天文数字一样的非常小。借由同样的论证，快速排序的递归平均只要2(2log₂ n)的调用深度就会终止。但是如果它的平均调用深度是O(log n)且每一阶的调用树状过程最多有 n 个元素，则全部完成的工作量平均上是乘积，也就是 O(n log n)。

平均复杂度

即使如果我们无法随机地选择基准数值，对于它的输入之所有可能排列，快速排序仍然只需要O(n log n)时间。因为这个平均是简单地将输入之所有可能排列的时间加总起来，除以n这个因子，相当于从输入之中选择一个随机的排列。当我们这样作，基准值本质上就是随机的，导致这个算法与乱数快速排序有一样的运行时间。

更精确地说，对于输入顺序之所有排列情形的平均比较次数，可以借由解出这个递归关系式可以精确地算出来。

$C(n) = n - 1 + \frac{1}{n} \sum_{i=0}^{n-1} (C(i)+C(n-i-1)) = 2n \ln n = 1.39n \log_2 n.$

在这里，n-1 是分区所使用的比较次数。因为基准值是相当均匀地落在排列好的数列次序之任何地方，总和就是所有可能分区的平均。

这个意思是，平均上快速排序比理想的比较次数，也就是最好情况下，只大约比较糟39%。这意味着，它比最坏情况较接近最好情况。这个快速的平均运行时间，是快速排序比其他排序算法有实际的优势之另一个原因。

空间复杂度

被快速排序所使用的空间，依照使用的版本而定。使用原地（in-place）分区的快速排序版本，在任何递归调用前，仅会使用固定的額外空間。然而，如果需要产生O(log n)嵌套递归调用，它需要在他们每一个存储一个固定数量的信息。因为最好的情况最多需要O(log n)次的嵌套递归调用，所以它需要O(log n)的空间。最坏情况下需要O(n)次嵌套递归调用，因此需要O(n)的空间。

然而我们在这里省略一些小的细节。如果我们考虑排序任意很长的数列，我们必须要记住我们的变量像是left和right，不再被认为是占据固定的空间；也需要O(log n)对原来一个n项的数列作索引。因为我们在每一个堆栈框架中都有像这些的变量，实际上快速排序在最好跟平均的情况下，需要O(log² n)空间的比特数，以及最坏情况下O(n log n)的空间。然而，这并不会太可怕，因为如果一个数列大部份都是不同的元素，那么数列本身也会占据O(n log n)的空间字节。

非原地版本的快速排序，在它的任何递归调用前需要使用O(n)空间。在最好的情况下，它的空间仍然限制在O(n)，因为递归的每一阶中，使用与上一次所使用最多空间的一半，且

\sum_{i=0}^{\infty} \frac{n}{2^i} = 2n.

它的最坏情况是很恐怖的，需要

\sum_{i=0}^n (n-i+1) = \Theta (n^2)

空间，远比数列本身还多。如果这些数列元素本身自己不是固定的大小，这个问题会变得更大；举例来说，如果数列元素的大部份都是不同的，每一个将会需要大约O(log n)为原来存储，导致最好情况是O(n log n)和最坏情况是O(n² log n)的空间需求。

最差时间复杂度	$\Theta(n^2)$
最优时间复杂度	$\Theta(n\log n)$
平均时间复杂度	$\Theta(n\log n)$
最差空间复杂度	根据实现的方式不同而不同

快速排序动态图：

实现代码：

[html]view plain copy 
 print?
package com.baobaotao.test;  
/**  
 * 排序研究  
 * @author benjamin(吴海旭)  
 * @email benjaminwhx@sina.com / 449261417@qq.com  
 *  
 */  
public class Sort {  
      
    /**  
     * 快速排序实现  
     * @param array  
     * @param low  
     * @param high  
     */  
    public static void quickSort(int[] array, int low, int high) {  
        if(low < high) {  
            int pivot = partition(array, low, high);  
               
            quickSort(array, low, pivot - 1);  
              
            quickSort(array, pivot + 1, high);  
        }  
    }  
      
    /**  
     * 根据传入的最低位和最高位分割数组  
     * @param array 待排序数组  
     * @param low   数组下标下界  
     * @param high  数组上标上界  
     * @return pivot  
     */  
    public static int partition(int[] array, int low, int high) {  
        //第一个元素所在位置  
        int p_pos = low ;  
        //采用第一个元素为轴  
        int pivot = array[p_pos] ;  
        for (int i = low + 1; i <= high; i++) {  
            if (array[i] < pivot) {              
                p_pos++;  
                swap(array, p_pos, i);   
            }  
   
        }  
        swap(array, low, p_pos);  
   
        return p_pos;  
    }  
      
    /**  
     * 按从小到大的顺序交换数组  
     * @param a 传入的数组  
     * @param b 传入的要交换的数b  
     * @param c 传入的要交换的数c  
     */  
    public static void swap(int[] a, int b, int c) {  
        if(b == c) return ;  
        int temp = a[b] ;  
        a[b] = a[c] ;  
        a[c] = temp ;   
    }  
      
    /**  
     * 打印数组  
     * @param array  
     */  
    public static void printArr(int[] array) {  
        for(int c : array) {  
            System.out.print(c + " ");  
        }  
        System.out.println();  
    }  
      
    public static void main(String[] args) {  
        int[] number={11,95,45,15,78,84,51,24,12} ;  
        quickSort(number, 0, number.length-1) ;  
        printArr(number) ;  
    }  
}  

转载请标注：http://blog.csdn.net/benjamin_whx/article/details/42460883

排序高级之交换排序_快速排序

优化的排序算法

正规的分析

乱数快速排序的期望复杂度

平均复杂度

空间复杂度

热门文章

最新文章

相关电子书