原理

對(duì)于一個(gè)數(shù)組x，快速排序流程如下：

1. 確定分界點(diǎn)a，可以取x[l]、x[r]、x[l + r / 2]、隨機(jī)（四種都可以）
2. 調(diào)整區(qū)間，使得：區(qū)間被分成 <= a 和 >= a的兩部分，左邊 <= a，右邊 >= a（注意，a不一定在原來(lái)的位置了）
3. 遞歸處理左右兩邊

重點(diǎn)在于第二步調(diào)整區(qū)間上。

做法是：在區(qū)間[l, r]中，指定兩個(gè)指針i、j。

• 當(dāng)i指向的數(shù) < a的時(shí)候，i往右移動(dòng)
• 當(dāng)j指向的數(shù) > a的時(shí)候，j往左移動(dòng)

當(dāng)i和j停下來(lái)的時(shí)候，說(shuō)明x[i] >= a，x[j] <= a，則x[i] >= x[j]。那根據(jù)我們的想要實(shí)現(xiàn)的目的，要保證左邊 <= a，右邊 >= a，也就是x[i] <= x[j]。因此，需要將x[i]與x[j]交換。

復(fù)雜度

代碼

import java.util.*;
import java.io.*;class Main {public static void quick(int[] x, int l, int r) {if (l >= r) return ;int a = x[l + r >> 1], i = l - 1, j = r + 1;while (i < j) {/**內(nèi)層的循環(huán)不能加  i < j原因：如果加了i < j，那么兩個(gè)do while之后，i = j。此時(shí)，如果x[j] > a，而后續(xù)的遞歸就會(huì)出問(wèn)題，因?yàn)橐ＷC[l, j]的數(shù)都 < a所以原則就是，最后外層循環(huán)退出的時(shí)候，要保證i > j，不能i = j*/do i ++ ; while (x[i] < a);do j -- ; while (x[j] > a);if (i < j) {int t = x[i];x[i] = x[j];x[j] = t;}}quick(x, l, j);quick(x, j + 1, r);}public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int[] x = new int[n];for(int i = 0; i < n; i ++ ) x[i] = sc.nextInt();quick(x, 0, n - 1);for(int i = 0; i < n; i ++ ) System.out.print(x[i] + " ");}
}