Johnny

/**
 * @author sikaijian
 */
public class QuickSort {
    
    /**
     * 快速排序算法实现
     * @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(" ");
        }
    }
}