核心思想

• 每一次循環(huán)指定一個元素，在循環(huán)結束后將這個元素放到它的"歸屬"位置
  • 比如升序排序，選定序列第一個元素為要"歸位"的元素，則從序列兩端開始往中間搜索，左邊找到第一個比要"歸位"的元素大的時候停止，右邊找到第一個比要"歸位"的元素小的時候停下，然后交換此時左右"游標"所指向的元素，交換后游標繼續(xù)向中間移動
  • 重復操作，直到左右游標相遇，交換要"歸位"的元素和"游標相遇的位置的元素"，該位置左邊全部都比它小，右邊全部比它大，這樣就完成了一個元素的"歸位"
  • 每一次將一個元素歸位之后，就把這個元素的左邊和右邊分成兩組，重復上述操作，直到所有元素歸位

比如數組{4, 2, 5, 6, 7, 1, 3}，要將4歸位
右邊找到3比4小，左邊找到5比4大，則交換3和5
{4, 2, 3, 6, 7, 1, 5}，然后繼續(xù)找，右邊又找到1比4小，左邊找到6比4大，交換1和6
{4, 2, 3, 1, 7, 6, 5}，然后右游標繼續(xù)往中間走，沒找到新的"小"的元素時就碰到了左游標，位置是1那里，此時交換4和1
{1, 2, 3, 4, 7, 6, 5}，此時發(fā)現4已經被成功"歸位"，左邊的數都比4小，右邊都比4大
然后把數組以4為分界線劃分開，{1, 2, 3, 4}，{7, 6, 5}
第二個數組{7, 6, 5}要將7歸位，右邊找到5比7小，左邊沒找到比7大的，于是往右走，在5的地方與右游標相遇，于是交換7和5，{5, 6, 7}
此時就完成了排序

算法實現

建議復制完整代碼，然后看具體步驟

完整代碼

import java.util.Arrays;

public class QuickSortDemo {
    private static void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    private static void quickSort(int[] nums, int start, int end) {
        if (start >= end) {
            return;
        }
        int i = start;
        int j = end;
        while (i < j) {
            while (i < j && nums[j] >= nums[start]) {
                j--;
            }
            while (i < j && nums[i] <= nums[start]) {
                i++;
            }
            swap(nums, i, j);
        }
        swap(nums, i, start);
        quickSort(nums, start, i - 1);
        quickSort(nums, j + 1, end);
    }

    public static void main(String[] args) {
        int[] nums = {1, 4, 7, 5, 2, 6, 3, 8, 9, 1, 4, 7, 8, 5, 2, 3, 1, 4};
        System.out.println(Arrays.toString(nums));
        quickSort(nums, 0, nums.length - 1);
        System.out.println(Arrays.toString(nums));
    }
}

具體步驟

• void swap(int[] nums, int i, int j) 是一個輔助方法，交換數組的兩個元素
• void quickSort(int[] nums, int start, int end) 是排序方法
  • start和end是在給定的序列最左端和最右端索引，然后設置"游標"分別指向start和end，分別叫索引i，索引j，nums[start]就是每輪要歸位的數，暫且稱為"基準數"
  • 只要兩個游標不相遇while (i < j)
    • 內層循環(huán)條件也要限定while (i < j)，如果游標在找到滿足條件的元素之前，就已經相遇，則及時停下
    • while (i < j && nums[j] >= nums[start]) { j--; }從右邊開始(后面解釋為什么從右邊開始)，j向左移動，只要不是比基準數小，就繼續(xù)移動
    • while (i < j && nums[i] <= nums[start]) { i++; }從左邊往中間搜索，i向右移動，只要不是比基準數大，就繼續(xù)移動
    • swap(nums, i, j)交換兩個游標的指向的數
  • swap(nums, i, start)完成循環(huán)結束后，交換游標i所在元素(j也行，已經指向同個元素)和基準數
  • 然后以基準數為界限分割數組，以分割后的的數組為待排序序列，遞歸調用方法，quickSort(nums, start, i - 1)，quickSort(nums, j + 1, end);
  • 方法最開始的if (start >= end) { return; }就是遞歸終止條件，當傳入分割數組的參數左端游標和右端游標重疊，則只有一個元素

避免踩坑

現在就解釋一下為什么從右邊開始

假設數組{4, 1, 2, 3, 5}，基準數是4，從左邊開始往右找比4大的數，發(fā)現只有最右邊滿足，直接就游標碰面在5的位置，交換5和4，交換后{5, 1, 2, 3, 4}發(fā)現與我們想法是不符合的
如果從右邊開始，則交換的是游標相遇的3，{3, 1, 2, 4, 5}則符合條件