[数据结构与算法]快速排序 Java模板

快速排序Java模板
详情参考 https://www.acwing.com/problem/content/787/
https://www.acwing.com/solution/content/2096/

快速排序的整体过程，动态变化流程

以从小到大排序为例

• 选择一个目标参考值$pivit$，通常课本上会说选择数组的第一个元素，但是如果本身数组就已经是从小到大有序了的话，这个时候效率是最差的，会退化到$O(n^2)$。因此我们这里选择中间位置的元素作为参考值

通常的、没有经过充分考虑的选择是将第一个元素做为"基准“。如果输入书随机的，那么这是可以接受的，但是如果输入是预排序的或是反序的，那么这样的”基准“就是一个劣质的分割，因为所以的元素不是被划入S1就是被划入S2。实际上，如果第一个元素用作”基准“而且输入是预先排序的，那么快速排序花费的时间将是二次的，可是实际上却没干什么事，因此，使用第一个元素作为”基准“是绝对糟糕的。

• 从前往后找到一个不比目标元素值小的元素$nums[i]$
• 从后往前找到一个不必目标元素值大的元素$nums[j]$
• 如果$i<j$，那么直接进行交换$nums[i]$和$nums[j]$的值
• 递归处理从$l$到$j$，以及从$j+1$到$r$的

import java.util.*;
import java.io.*;

public class Main {
    
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(reader.readLine());
        int[] arr = new int[n];
        String[] s = reader.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(s[i]);
        }
        quickSort(arr, 0, n - 1);
        for (int i = 0; i < n; i++) {
            writer.write(arr[i] + " ");
        }
        writer.write("\n");
        writer.flush();
        writer.close();
        reader.close();
    }
    
    public static void quickSort(int[] q, int l, int r) {
        if (l >= r)  {
            return;
        }
        // 取数组的中间位置的元素作为参考对象。
        // 假设原数组本身就是有序的，那么以数组中间位置元素记录的话，最坏情况下时间复杂度也只有O(n*n/2)
        int pivit = q[l + r >> 1];
        int i = l - 1;
        int j = r + 1;
        while (i < j) {
            do {
                i++;
            } while (pivit > q[i]);
            do {
                j--;
            } while (pivit < q[j]);
            if (i < j) {
                int tmp = q[i];
                q[i] = q[j];
                q[j] = tmp;
            }
        }
        quickSort(q, l, j);
        quickSort(q, j + 1, r);
    }
}