当前位置： 首页 > article >正文

随机快速排序

article 2025/3/13 15:33:05

随机快速排序
在这里插入图片描述

经典随机快速排序

// 随机快速排序，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区域的最后一个数字是x
	public 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、last
		int 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;
        }
        //求随机值x
        int 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循环的范围不同，主要是为了格式化输出，避免在最后一个数字后面多输出一个空格：

  1. 输入时: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)
  1. 随机快速排序 （x不固定）
    随机行为根据期望估计 时间复杂度O(N*logN) 空间复杂度O(logN)

至于为什么选择随机快速排序而不选择快速排序，因为测试数据可以轻易地构造，让每次选中间的数排序起来最难受！


http://www.kler.cn/a/582910.html

相关文章：

  • 我与DeepSeek读《大型网站技术架构》（12）-网购秒杀系统架构设计案例分析
  • JVM学习-类文件结构 类加载
  • FX-std::vector
  • Postgresql中null值和空字符串举例详解例子解析
  • SpringBoot 实现接口数据脱敏
  • 办公常用自动化工具
  • 【C++】STL全面简介与string类的使用(万字解析)
  • 【2025】基于springboot+vue的汽车销售试驾平台（源码、万字文档、图文修改、调试答疑）
  • 前：vue 后：django 部署：supervisor+nginx 流程及部分问题简记
  • python编写的一个打砖块小游戏
  • 基于AI智能算法的无人机城市综合治理
  • 计算机操作系统（一） 什么是操作系统
  • 安卓应用架构模式 MVC MVP MVVM有什么区别？
  • 多云环境中的大数据部署：从挑战到最佳实践
  • Vscode工具开发Vue+ts项目时vue文件ts语法报错-红波浪线等
  • 关于Java的入门
  • 解锁 Postman：下载安装与账户注册使用的全攻略，踏上测试新征程
  • Java后端高频面经——计算机网络
  • hadoop第3课（hdfs shell常用命令）
  • word排版：段内公式由于固定行间距显露不出的问题