【排序】快速排序

原理

对于一个数组x，快速排序流程如下：

1. 确定分界点a，可以取x[l]、x[r]、x[l + r / 2]、随机（四种都可以）
2. 调整区间，使得：区间被分成 <= a 和 >= a的两部分，左边 <= a，右边 >= a（注意，a不一定在原来的位置了）
3. 递归处理左右两边

重点在于第二步调整区间上。

做法是：在区间[l, r]中，指定两个指针i、j。

• 当i指向的数 < a的时候，i往右移动
• 当j指向的数 > a的时候，j往左移动

当i和j停下来的时候，说明x[i] >= a，x[j] <= a，则x[i] >= x[j]。那根据我们的想要实现的目的，要保证左边 <= a，右边 >= a，也就是x[i] <= x[j]。因此，需要将x[i]与x[j]交换。

复杂度

代码

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) {/**内层的循环不能加  i < j原因：如果加了i < j，那么两个do while之后，i = j。此时，如果x[j] > a，而后续的递归就会出问题，因为要保证[l, j]的数都 < a所以原则就是，最后外层循环退出的时候，要保证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] + " ");}
}