Quick Sort

Quick Sort 是將陣列依某個 key，分成較大的部份和較小的部份，再將兩部份分別排序即可。因此，排序時會出現兩個集團，分別是較大和較小的部分。集團會再分成更小的集團。當集團小到某個程度時，是以 insertion sort 排序，就不再分成更小的集團了。

public class QuickSortApplet extends SortApplet {

    public void run() {
        int l = 0, r = number - 1;
        int[] stack = new int[50];
        int top = 0;
        int i;

        while(true) {
            while(r > l) {
                if(r - l <= 10) {
                    insertion(l, r);
                    break;
                }

                i = partition(l, r);
                if(i - l > r - i) {
                    stack[top++] = l;
                    stack[top++] = i - 1;
                    l = i + 1;
                }
                else {
                    stack[top++] = i + 1;
                    stack[top++] = r;
                    r = i - 1;
                }
            }
            if(top == 0)
                break;
            r = stack[--top];
            l = stack[--top];
        }
    }

    private int partition(int l, int r) {
        int m = (l + r) / 2;
        if(getData(l) > getData(m))
            swapData(l, m);
        if(getData(l) > getData(r))
            swapData(l, r);
        if(getData(m) > getData(r))
            swapData(m, r);
        swapData(m, r - 1);

        m = r - 1;
        int v = getData(m);

        l++;
        r -= 2;

        while(true) {
            while(getData(l) < v)
                l++;
            while(getData(r) > v)
                r--;
            if(l >= r)
                break;
            swapData(l, r);
            l++;
            r--;
        }
        swapData(l, m);

        return l;
    }

    private void insertion(int l, int r) {
        int i, j, v;

        for(i = l + 1; i <= r; i++) {
            v = getData(i);
            j = i;
            while(j > l && getData(j-1) > v) {
                copyData(j, j-1);
                j--;
            }
            setData(j, v);
        }
    }
}