【排序】快速排序

原理

对于一个数组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] + " ");
    }
}