排序—快速排序

快速排序：

　　1、從數組中隨便選出一個數（其實一般用第一個數）作為本次迴圈的比較基數，然後走一趟，把所有比基數小的數放在該基數的左邊，把大於該基數的數放在該基數的右邊（排序結果有小到大，反之反之）。

　　　　（該基數在數組中的腳標是變動的，不要考慮比該基數小（大）的數較多，在其左（右）邊放不下的弱智腦殘問題）

      2、通過遞歸來實現，把小於該基數的數（或者大於該基數的數）作為一個新的數組，重覆第一步操作。

            不熟練遞歸的看這裡： http://www.cnblogs.com/PerkinsZhu/p/5668218.html

重點來了：怎麼通過迴圈一趟把小於該基數的數移動到其左邊，大於該基數的數移動到其右邊呢？怎麼辦呢？這是個問題！！！

               這麼乾：取第一個數為基數，然後從數組的右邊向左邊依次取數比較，一直找到比基數小的數（記錄該數的index為right），然後交換兩數位置，停止從右向左尋找。

　　　　　　　　　　開始從左向右尋找，找到比該基數大的數（記錄該數index為left），然後交換兩數的位置，停止從左向右尋找。

　　　　　　　　　  開始從右向左尋找……開始從左向右尋找……   明白嗎？一直迴圈，終止條件是：數組中的除基數外所有的數都與該基數比較過，也就是right=left。

運行示例：

原數組：　　　　　21、8、2、18、0、9、27、12、5、24、
第0次迴圈排序結果: 5、8、2、18、0、9、27、12、21、24、
第1次迴圈排序結果: 5、8、2、18、0、9、21、12、27、24、
第2次迴圈排序結果: 5、8、2、18、0、9、12、21、27、24、
第3次迴圈排序結果: 0、8、2、18、5、9、12、21、27、24、
第4次迴圈排序結果: 0、5、2、18、8、9、12、21、27、24、
第5次迴圈排序結果: 0、2、5、18、8、9、12、21、27、24、
第6次迴圈排序結果: 0、2、5、12、8、9、18、21、27、24、
第7次迴圈排序結果: 0、2、5、9、8、12、18、21、27、24、
第8次迴圈排序結果: 0、2、5、8、9、12、18、21、27、24、
第9次迴圈排序結果: 0、2、5、8、9、12、18、21、24、27、

好了，看代碼吧：

public void callQuickSort(int[] array) {
        printArray("原數組：", array);
        quickSort(array, 0, array.length - 1);
    }

    public void quickSort(int[] array, int left, int right) {
        if (left >= right)
            return;
        int index = qSort(array, left, right);
        quickSort(array, left, index);
        quickSort(array, index + 1, right);
    }

    private int qSort(int[] array, int left, int right) {
        int mid = left;
        int temp;
        while (left < right) {
            if (mid != right) {
                if (array[mid] > array[right]) {
                    temp = array[right];
                    array[right] = array[mid];
                    array[mid] = temp;
                    mid = right;
                    printArray("第" + time++ + "次迴圈排序結果: ", array);
                } else {
                    right--;
                }
            } else {
                if (array[left] > array[mid]) {
                    temp = array[left];
                    array[left] = array[mid];
                    array[mid] = temp;
                    mid = left;
                    printArray("第" + time++ + "次迴圈排序結果: ", array);
                } else {
                    left++;
                }
            }

        }
        return mid;
    }