快速排序

快速排序是由東尼·霍爾所發展的一種排序算法。在平均狀況下，排序 n 個項目要Ο(n log n)次比較。在最壞狀況下則需要Ο(n2)次比較，但這種狀況並不常見。事實上，快速排序通常明顯比其他Ο(n log n) 演算法更快，因為它的內部循环（inner loop）可以在大部分的架構上很有效率地被實作出來，且在大部分真實世界的資料，可以決定設計的選擇，減少所需時間的二次方項之可能性。

/**
 * Created by IntelliJ IDEA.
 * User: mayday
 * Date: 12-3-22
 * Time: 下午4:21
 */
public class Qsort {

    static int[] a = new int[20];

    public static void main(String[] args) {
        for (int i = 0; i < a.length; i++)
            a[i] = (int) (Math.random() * 200);
        for (int i : a)
            System.out.print(i + " ");
        System.out.println();
        qsort(0, a.length-1);
        for (int i : a)
            System.out.print(i + " ");

    }

    private static void qsort(int l, int u) {
        if (u - l < 1)
            return;
        swap(l, randint(l, u));//选取数组中随机一个元素作为划分元素
        int t = a[l];
        int i = l;
        int j = u + 1;
        while (true) {
            do i++; while (i <= u && a[i] < t);//从左侧开始遍历,直到找到一个大于等于t的或者到达最右侧
            do j--; while (a[j] > t);//从右侧开始遍历,找到一个小于等于t的
            if (i > j)//当交叉时 break
                break;
            swap(i, j);//不交叉则将左侧比t大的与右侧比t小的交换
        }
        swap(l, j);//循环终止时,交换a[l]和a[j]
        qsort(l, j - 1);//对左侧递归调用qsort
        qsort(j + 1, u);//对右侧递归调用qsort
    }

    private static void swap(int x, int y) {
        int temp = a[x];
        a[x] = a[y];
        a[y] = temp;
    }

    private static int randint(int a, int b) {
        //产生a与b之间的随机数
        return a + (int) (Math.random() * 100) % (b - a + 1);
    }
}

　　Reference:

Quicksort is Optimalby Robert SedgewickandJon Bentley, Knuthfest, Stanford University, January, 2002.

快速排序-维基百科