快速排序Java模板
详情参考 https://www.acwing.com/problem/content/787/
https://www.acwing.com/solution/content/2096/
快速排序的整体过程，动态变化流程
以从小到大排序为例
- 选择一个目标参考值p i v i t pivitpivit，通常课本上会说选择数组的第一个元素，但是如果本身数组就已经是从小到大有序了的话，这个时候效率是最差的，会退化到O ( n 2 ) O(n^{2} )O(n2)。因此我们这里选择中间位置的元素作为参考值
通常的、没有经过充分考虑的选择是将第一个元素做为"基准“。如果输入书随机的，那么这是可以接受的，但是如果输入是预排序的或是反序的，那么这样的”基准“就是一个劣质的分割，因为所以的元素不是被划入S1就是被划入S2。实际上，如果第一个元素用作”基准“而且输入是预先排序的，那么快速排序花费的时间将是二次的，可是实际上却没干什么事，因此，使用第一个元素作为”基准“是绝对糟糕的。
- 从前往后找到一个不比目标元素值小的元素n u m s [ i ] nums[i]nums[i]
- 从后往前找到一个不必目标元素值大的元素n u m s [ j ] nums[j]nums[j]
- 如果i < j i < ji<j，那么直接进行交换n u m s [ i ] nums[i]nums[i]和n u m s [ j ] nums[j]nums[j]的值
- 递归处理从l ll到j jj，以及从j + 1 j + 1j+1到r rr的
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); } }
