java快速排序詳解

快速排序

1.排序思路

（1）快速排序本質相當于找到數組中的“基準數”在數組中的“中間”位置，然後從“中間”位置為分界線，分割成“左右”兩個小的數組，在這個小的數組中繼續遞歸上述操作。

（2）所謂“中間”位置：将比基準數大的資料放在基準數右邊，把基準數小的放在左邊。

（3）所謂“基準數”：随便在數組兩端選擇一個，一般選擇最左邊的數。

2.代碼思路

（1）其實所有排序的本質是找到數組中的數在一個“合适”的位置的過程：快速排序就是在找基準數在數組“中間”位置的過程，可以首先想到指針。

（2）如果選擇最左的數作為基準數，則從右到左比較，反之亦然。

（3）如果比基準數大（或等于）則移動最右端的指針指向左一步，并用指針處的值和基準數比較，直到遇到比基準數小的數，則停止移動指針。

（4）待（3）步驟停止移動指針後，從左到右進行比較，如果比基準數小（或等于），則移動最左端的指針向右移動一步，并用指針處的值和基準數比較，直到遇到比基準數大的數，則停止移動指針。

（5）此時如果指針未相遇則将指針停留所在的數進行交換，然後重複（3）和（4）步驟，直到指針重合。

（6）當指針重合，退出（3）（4）（5）循環，将指針重合處的數和基準數進行交換位置。

（7）此時完成了一次将數組中比基準數小的數放在左邊，将比基準數大的數放在右邊的過程，為這個基準數找到了一個“中間”位置。

（8）以指針重合處作為分隔處，将隔開的“左邊部分”的數組和“右邊部分”的數組繼續循環（4）（5）（6）（7）（8）步驟，直到不可分割為止。

3.代碼示例

@Test
    public void testQuickSort() {
        int[] arr = {1111,222,31231,12312111,1231231231,123};
        qs(arr, 0, arr.length - 1);
        System.err.println(Arrays.toString(arr));
    }

    public static void qs(int[] arr, int left, int right) {
        if (left < right) {
        	//低位指針
            int low = left;
            //高位指針
            int high = right;
            //選擇基準數
            int key = arr[left];
            while (low < high) {
                //從右到左如果比基準數大于等于左移，遇到小于基準數就停下來
                while (low < high && arr[high] >= key) {
                    high--;
                }
                //從左到右如果比基準數小于等于就右移，遇到大于基準數就停下來
                while (low < high && arr[low] <= key) {
                    low++;
                }
                //交換2個指針處對應的數
                if (low < high) {
                    int temp = arr[high];
                    arr[high] = arr[low];
                    arr[low] = temp;
                }
            }
            //交換重合數和基準數
            arr[left] = arr[low];
            arr[low] = key;
            qs(arr, left, low - 1);
            qs(arr, low + 1, right);
        }
    }
           

ps：預設排序為升序