Johnny

/**
 * @author sikaijian
 */
public class QuickSort {
    
    /**
     * 快速排序算法實現(xiàn)
     * @param data 待排序數組
     * @param left 左邊界 初始0
     * @param right 右邊界 初始數組長度-1
     * @author sikaijian
     */
    public static void sort(int[] data, int left, int right) {
        if (left > right)
            return;
        int pHead = left;  // 頭部指針
        int pTail = right;  // 尾部指針
        int key = data[left];  // 哨兵

        while (pHead < pTail) {
            // 從右往左遍歷，找到比key小的數，放到前面
            while (pHead < pTail && data[pTail] > key) pTail--;
            if (pHead < pTail) data[pHead++] = data[pTail];
            
            // 從左往右遍歷，找到比key大的數，放到后面
            while (pHead < pTail && data[pHead] < key) pHead++;
            if (pHead < pTail) data[pTail--] = data[pHead];
        }
        
        data[pHead] = key; // 歸位
        
        sort(data, left, pHead-1);  // 排序左邊的數組
        sort(data, pHead+1, right);  // 排序右邊的數組
    }
    
    /**
     * 測試代碼
     * @param args
     */
    public static void main(String[] args) {
        int[] data = new int[] { 49, 23, 65, 13, 38, 96, 12, 33, 88, 123, 22,
                11, 9, 55 };

        for (int t : data) {
            System.out.print(t);
            System.out.print(" ");
        }
        System.out.println();
        System.out.println("------------------------------");
        QuickSort.sort(data, 0, data.length - 1);

        for (int t : data) {
            System.out.print(t);
            System.out.print(" ");
        }
    }
}