随机快速排序
经典随机快速排序
// 随机快速排序，acm练习风格
// 测试链接 : https://www.luogu.com.cn/problem/P1177
// 务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成"Main"，可以直接通过import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;public class Code01_QuickSort {public static int MAXN = 100001;public static int[] arr = new int[MAXN];public static int n;public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));StreamTokenizer in = new StreamTokenizer(br);PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));in.nextToken();n = (int) in.nval;for (int i = 0; i < n; i++) {in.nextToken();arr[i] = (int) in.nval;}quickSort2(0, n - 1);for (int i = 0; i < n - 1; i++) {out.print(arr[i] + " ");}out.println(arr[n - 1]);out.flush();out.close();br.close();}// 随机快速排序经典版(不推荐)// 甚至在洛谷上测试因为递归开太多层会爆栈导致出错public static void quickSort1(int l, int r) {// l == r，只有一个数// l > r，范围不存在，不用管if (l >= r) {return;}// 随机这一下，常数时间比较大// 但只有这一下随机，才能在概率上把快速排序的时间复杂度收敛到O(n * logn)// l......r 随机选一个位置，x这个值，做划分int x = arr[l + (int) (Math.random() * (r - l + 1))];int mid = partition1(l, r, x);quickSort1(l, mid - 1);quickSort1(mid + 1, r);}// 已知arr[l....r]范围上一定有x这个值// 划分数组 <=x放左边，>x放右边// 并且确保划分完成后<=x区域的最后一个数字是xpublic static int partition1(int l, int r, int x) {// a : arr[l....a-1]范围是<=x的区域// xi : 记录在<=x的区域上任何一个x的位置，哪一个都可以int a = l, xi = 0;for (int i = l; i <= r; i++) {if (arr[i] <= x) {swap(a, i);if (arr[a] == x) {xi = a;}a++;}}swap(xi, a - 1);return a - 1;}public static void swap(int i, int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}// 随机快速排序改进版(推荐)// 可以通过所有测试用例public static void quickSort2(int l, int r) {if (l >= r) {return;}// 随机这一下，常数时间比较大// 但只有这一下随机，才能在概率上把快速排序的时间复杂度收敛到O(n * logn)int x = arr[l + (int) (Math.random() * (r - l + 1))];partition2(l, r, x);// 为了防止底层的递归过程覆盖全局变量// 这里用临时变量记录first、lastint left = first;int right = last;quickSort2(l, left - 1);quickSort2(right + 1, r);}// 荷兰国旗问题public static int first, last;// 已知arr[l....r]范围上一定有x这个值// 划分数组 <x放左边，==x放中间，>x放右边// 把全局变量first, last，更新成==x区域的左右边界public static void partition2(int l, int r, int x) {first = l;last = r;int i = l;while (i <= last) {if (arr[i] == x) {i++;} else if (arr[i] < x) {swap(first++, i++);} else {swap(i, last--);}}}}
荷兰国旗问题优化
import java.io.*;public class Main{public static int MAXN = 100001;public static int arr[] = new int[MAXN];public static int n ;public static void main(String[] args) throws IOException{BufferedReader br = new BufferedReader(new InputStreamReader(System.in));StreamTokenizer in = new StreamTokenizer(br);PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));in.nextToken();n = (int)in.nval;//输入for(int i = 0;i < n ;i++){in.nextToken();arr[i] = (int)in.nval;}quickSort(0,n-1);//输出for(int i = 0;i<n-1;i++){out.print(arr[i] + " ");}out.print(arr[n-1]);out.flush();out.close();}public static void quickSort(int l,int r){if(l >= r){return;}//求随机值xint x = arr[l + (int)(Math.random()*(r -l +1))];partition(l,r,x);int left = a;int right = b;quickSort(l,left - 1);quickSort(right + 1,r);}public static int a;public static int b;public static void partition(int l,int r,int x){a = l;b = r;int i = l;while(i<=b){if(arr[i] == x){i++;}else if(arr[i]< x){//交换arr[i]和arr[a]; a++;i++swap(i,a);a++;i++;}else{//交换arr[i]和arr[b],i不变;b--;swap(i,b);b--;}}}public static void swap(int i,int j){int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}
}实现细节1：
在输入和输出数组的时候，for循环的范围不同，主要是为了格式化输出，避免在最后一个数字后面多输出一个空格：
- 输入时:i < n
in.nextToken();
n = (int) in.nval;
for (int i = 0; i < n; i++) {in.nextToken();arr[i] = (int) in.nval;
}
-
这里for循环中
i < n是正常的，因为要读取所有n个元素，所以i从 0 到 n - 1 都需要复制给arr[i]。 -
这是标准的遍历数组方式，确保所有元素都被正确读取。
-
输出时:i < n -1
for (int i = 0; i < n - 1; i++) {out.print(arr[i] + " ");}out.println(arr[n - 1]);
- 这里for循环中
i < n -1,意味着for循环只输出前n-1个元素，并在他们之间加上 空格" "。 - 最后单独输出
arr[n - 1]。这样 不会在最后一个元素后面多加一个空格。
小结：
✔ 输入：for (int i = 0; i < n; i++)确保 所有元素都被读取。
✔ 输出： for (int i = 0; i < n - 1; i++) 避免最后一个元素后面多空格，然后 println(arr[n - 1]) 处理最后一个元素。
这样可以保证输出格式正确，特别是在 OJ 判题系统 中不会因为末尾额外的空格导致格式错误！
实现细节2：
| 代码 | 作用 |
|---|---|
| out.flush(); | 强制将缓冲区数据输出，防止数据丢失 |
| out.close(); | 关闭 PrintWriter，释放输出资源 |
| br.close(); | 关闭 BufferedReader，释放输入资源 |
建议：
如果 out 是 System.out，close() 可以省略，因为 JVM 退出时会自动关闭。
但如果 out 关联文件，必须 close()，否则可能导致 文件写入不完整 或 文件句柄 泄漏。
两种快排：
- 快速排序（x固定）
最差情况 ：（x不靠近中点，在左右两侧） - 时间复杂度 O(n^2)
- 空间复杂度 O(n)
最好情况：(x靠近中点） - 时间复杂度O(N*logN)
- 空间复杂度O(logN)
- 随机快速排序 （x不固定）
随机行为根据期望估计 时间复杂度O(N*logN) 空间复杂度O(logN)
至于为什么选择随机快速排序而不选择快速排序，因为测试数据可以轻易地构造，让每次选中间的数排序起来最难受！
