排序--快速排序

http://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F

快速排序

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

算法

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

步骤为：

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

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

竞争的排序算法

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

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

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

Java实现

public class Quick
{
    public static <T extends Comparable<? super T>> void quick(T[] arr)
    {
        quickSort(arr, 0, arr.length - 1);
    }

    /**
     * 快速排序
     * 
     * @param arr an array of comparable items
     * @param left the left-most index
     * @param right the right-most index
     */
    public static <T extends Comparable<? super T>> void quickSort(T[] arr, int left, int right)
    {
        if(left >= right)
            return;
        T pivot = arr[left];
        int i = left, j = right, middle;
        while(i < j)
        {
            //小于中轴点的值移动到数列的左侧
            while(i < j && arr[j].compareTo(pivot) >= 0)
            {
                j--;
            }
            arr[i] = arr[j];
            //大于中轴点的值移动到数列的右侧
            while(i < j && arr[i].compareTo(pivot) <= 0)
            {
                i++;
            }
            arr[j] = arr[i];
        }
        arr[i] = pivot;//中轴点的值为pivot
        middle = i;//中轴点为i
        quickSort(arr, left, middle - 1);
        quickSort(arr, middle + 1, right);
    }

    public static void main(String[] args)
    {
        Integer[] arr = {212, 22, 22, 1, 23, 4, 5, 7, 890, 44, 22, 2, 5, 788, 444, 222, 11, 122, 3, 3, 44, 45, 43, 543, 2, 1, 68, 9};
        quick(arr);
        for(int i = 0; i < arr.length; i++)
        {
            System.out.print(arr[i] + " ");
        }
    }
}