快速排序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);}
}