【算法】---快速排序

参考

左神和神书算法导论.

学习前置

  • 了解并实现过快速排序。 笔者曾经在数据结构篇写过快速排序，现在面向算法篇快排。

快速排序

输入数据所有排列是等概率的， 这种情况对于实际工程上不会总是成立。朴素快速排序对于特定的输入很糟糕， 数组越是接近有序，那么朴素快速排序的效率就更低。最坏情况是 O ( n 2 ) O(n^2) O(n2)。
实际中，有人提出在快排中引入随机性，对抗特定输入的影响，转而研究期望运行时间。比如可以通过数组打乱算法，用随机化方法打乱数组，使得快排避免了输入序列的影响。
更简单的方法， 快速排序糟糕的时间复杂度究其原因在于 固定取数。
先前的快速排序篇说明了用三数取中法和过短序列穿插插入排序的过程优化。不过对于力扣上的sort an array这道题， 始终是很低的时间复杂度。
下面介绍经典的随机化快速排序写法，和左神介绍的荷兰化国旗法。

经典随机化快排

假设选中值5为枢轴， i遍历数组，如果发现小于等于5的元素，那么与a所处元素进行交换， a进行往后挪动一位。 a左边的[l,a-1]区间维护的是≤5的元素，那么循环结束时，a指向的就是>5的位置， 要返回a-1处的下标位置。
还需注意，由于我们选择值为枢轴，而不是数组下标。我们还需要找到满足值得对应下标，来与a-1处得元素进行交换，使得a-1处元素左右分别≤x，≥x。
在这里插入图片描述
可以修改下面代码中得MAX，和随机数生成范围来测试更多数据。
或者自行编写IO代码， 自主输入测试用例。

package class_2;

import java.util.Arrays;
import java.util.Random;
public class Coding_quickSort1 {
	public static void quickSort(int[] arr) {
		//处理特殊情况。
		if(arr==null || arr.length<2) {
			return ;
		}
		//主方法首次调用
		quick(arr,0, arr.length-1);
	}
	public static void quick(int[] arr, int l,int r) {
		//l==r, l>r直接返回， 不用处理。
		if(l>=r) {
			return ;
		}
		//随机取[l,r]的一个数nums[?]
		int x = arr[l+(int)(Math.random()*(r-l+1))];
		int pivot = partition(arr,l,r,x);
		quick(arr,l,pivot-1);
		quick(arr,pivot,r);
	}
	public static int partition(int[] arr,int l,int r,int x) {
		int i=l,xi=0;
		int a = i;
		//[l...a-1]为<=x的区间
		//[a...r]为>x的区间
		for(i=l;i<=r;i++) {
			if(arr[i]<=x) {
				//进行交换。
				swap(arr,a,i);
				if(arr[a]==x) {
					xi=a;//标记xi的坐标
				}
				a++;
			}
		}
		//将xi的元素作为分割点。
		swap(arr,a-1,xi);
		return a-1;
	}
	public static void swap(int[] arr,int i,int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
	public static int MAX = 25;
	public static void main(String[] args) {
		Random random = new Random(10000);
		int[] arr = new int[MAX];
		for(int i=0;i<MAX;i++) {
			arr[i] = random.nextInt(1000);
		}
		System.out.println("排序前:"+Arrays.toString(arr));
		quickSort(arr);
		System.out.println("排序后:"+Arrays.toString(arr));
	}
}

荷兰国旗快排

经典随机化快速排序的缺点是什么？
给你一个测试main函数，看看结果吧。

	public static int MAX = 3000;
	public static void main(String[] args) {
		  Random random = new Random(100);
	        int[] arr = new int[MAX];
	        System.out.printf("输入规模:%d\n",MAX);
	        // 测试重复数字的情况
	        for (int i = 0; i < MAX; i++) {
	            arr[i] = random.nextInt(10000);
	        }
	        System.out.println("排序前:" + Arrays.toString(arr));
	        long startTime = System.nanoTime();
	        quickSort(arr);
	        long endTime = System.nanoTime();
	        System.out.println("排序后:" + Arrays.toString(arr));
	        System.out.println("出现重复数字的情况的执行时间: " + (endTime - startTime) + " 纳秒");

	        // 测试无重复数字的情况
	        random.setSeed(0);
	        Set<Integer> set = new HashSet<>();
	        while (set.size() < MAX) {
	            set.add(random.nextInt(10000));
	        }
	        int i = 0;
	        for (int x : set) {
	            arr[i++] = x;
	        }
	        System.out.println("--------------------------------");
	        System.out.println("排序前:" + Arrays.toString(arr));
	        startTime = System.nanoTime();
	        quickSort(arr);
	        endTime = System.nanoTime();
	        System.out.println("排序后:" + Arrays.toString(arr));
	        System.out.println("不出现重复数字的情况的执行时间: " + (endTime - startTime) + " 纳秒");

	        // 测试完全相同的情况
	        Arrays.fill(arr, 5);
	        System.out.println("--------------------------------");
	        System.out.println("排序前:" + Arrays.toString(arr));
	        startTime = System.nanoTime();
	        quickSort(arr);
	        endTime = System.nanoTime();
	        System.out.println("排序后:" + Arrays.toString(arr));
	        System.out.println("出现完全相同的重复数字的情况的执行时间: " + (endTime - startTime) + " 纳秒");
	        System.out.println("--------------------------------");
	}
  • 第一种会出现重复数字。
  • 第二组测试，借助set去重。完全不重复的数字。
  • 第三组测试，完全相同的数字。
  • 随便看一组用例输出：
出现重复数字的情况的执行时间: 1377800 纳秒
不出现重复数字的情况的执行时间: 488300 纳秒
出现完全相同的重复数字的情况的执行时间: 6230400 纳秒

事实是，完全重复>部分重复>完全不重复。
完全重复的时间复杂度是 O ( n 2 ) O(n^2) O(n2), 因为上面经典算法，会将规模为n的数组序列，一直转化为n-1和1的规模。
怎么优化呢？
传统的快速排序，总是选择一个枢轴x，分为<=x，x,>=x的区间。问题在于x可能会重复， 为什么不能将x统一连续的放一起后续就不用处理了呢？
如下修改partition过程， 使其返回一个数对, 这里以一个自定义的内部类Tuple举例实现， 可以通过全局静态变量其它等实现。

public class Coding_quickSort2 {
	public static void quickSort(int[] arr) {
		if(arr==null || arr.length<2) {
			return ;
		}
		quick(arr,0, arr.length-1);
	}
	static class Tuple{
		int first;
		int last;
		public Tuple(int first,int last) {
			this.first = first;
			this.last = last;
		}
		public Tuple() {
			
		}
	}
	//考虑多线程可以放到主方法内实例化对象， 当作参数传递。
	public static Tuple tuple = new Tuple();//辅助partition。
	public static void quick(int[] arr, int l,int r) {
		//l==r, l>r直接返回， 不用处理。
		if(l>=r) {
			return ;
		}
		//随机取[l,r]的一个数 nums[?]
		int x = arr[l+(int)(Math.random()*(r-l+1))];
		
		partition(arr,l,r,x);
		quick(arr,l,tuple.first-1);
		quick(arr,tuple.last,r);
	}
	/**
	 * partition 方法的目的是根据给定的基准（pivot）将数组分成两部分：
	 * 一部分包含所有小于基准的元素，另一部分包含所有大于基准的元素。
	 * 该方法的返回结果是新的分区边界，以便在快速排序中递归调用。
	 * @param arr 数组
	 * @param l 左端点
	 * @param r 右端点
	 * @param x 随机选取的枢轴
	 */
	public static void partition(int[] arr, int l, int r, int x) {
	    tuple.first = l; // 小于区域的右边界
	    tuple.last = r;  // 大于区域的左边界
	    int i = l;       // 当前元素指针

	    while (i <= tuple.last) {
	        if (arr[i] == x) {
	            // 当前元素等于主元，移动指针
	            i++;
	        } else if (arr[i] < x) {
	            // 当前元素小于主元，交换到小于区域
	            swap(arr, tuple.first++, i++);
	        } else {
	            // 当前元素大于主元，交换到大于区域
	        	// 注意这里i不变。
	            swap(arr, tuple.last--, i);
	        }
	    }
	}
	public static void swap(int[] arr,int i,int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
	public static int MAX = 3000;
	public static void main(String[] args) {
		  Random random = new Random(100);
	        int[] arr = new int[MAX];
	        System.out.printf("输入规模:%d\n",MAX);
	        // 测试重复数字的情况
	        for (int i = 0; i < MAX; i++) {
	            arr[i] = random.nextInt(10000);
	        }
	        System.out.println("排序前:" + Arrays.toString(arr));
	        long startTime = System.nanoTime();
	        quickSort(arr);
	        long endTime = System.nanoTime();
	        System.out.println("排序后:" + Arrays.toString(arr));
	        System.out.println("出现重复数字的情况的执行时间: " + (endTime - startTime) + " 纳秒");

	        // 测试无重复数字的情况
	        random.setSeed(0);
	        Set<Integer> set = new HashSet<>();
	        while (set.size() < MAX) {
	            set.add(random.nextInt(10000));
	        }
	        int i = 0;
	        for (int x : set) {
	            arr[i++] = x;
	        }
	        System.out.println("--------------------------------");
	        System.out.println("排序前:" + Arrays.toString(arr));
	        startTime = System.nanoTime();
	        quickSort(arr);
	        endTime = System.nanoTime();
	        System.out.println("排序后:" + Arrays.toString(arr));
	        System.out.println("不出现重复数字的情况的执行时间: " + (endTime - startTime) + " 纳秒");

	        // 测试完全相同的情况
	        Arrays.fill(arr, 5);
	        System.out.println("--------------------------------");
	        System.out.println("排序前:" + Arrays.toString(arr));
	        startTime = System.nanoTime();
	        quickSort(arr);
	        endTime = System.nanoTime();
	        System.out.println("排序后:" + Arrays.toString(arr));
	        System.out.println("出现完全相同的重复数字的情况的执行时间: " + (endTime - startTime) + " 纳秒");
	        System.out.println("--------------------------------");
	}
}

出现重复数字的情况的执行时间: 1616100 纳秒
不出现重复数字的情况的执行时间: 7351300 纳秒
出现完全相同的重复数字的情况的执行时间: 28300 纳秒
经过·处理， 效率直接颠倒了， 重复数字越多处理越快。

sort an array
在这里插入图片描述

补充中ing, 再见， 感谢您的观看。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/886735.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Redis入门第一步：认识Redis与快速安装配置

Redis入门第一步：认识Redis与快速安装配置

认识Redis与快速安装配置&#x1f343; Redis是什么&#x1f432; 1.Redis的背景&#x1f38d; Redis&#xff08;Remote Dictionary Server&#xff09;译为"远程字典服务"&#xff0c;它是一款基于内存实现的键值型 NoSQL 数据库&#xff0c; 通常也被称为数据结…
阅读更多...
Python 从入门到实战33（使用MySQL）

Python 从入门到实战33（使用MySQL）

我们的目标是&#xff1a;通过这一套资料学习下来&#xff0c;通过熟练掌握python基础&#xff0c;然后结合经典实例、实践相结合&#xff0c;使我们完全掌握python&#xff0c;并做到独立完成项目开发的能力。 上篇文章我们讨论了数据库编程接口操作的相关知识。今天我们将学习…
阅读更多...
音视频入门

音视频入门

一个视频&#xff0c;一秒内普遍大于等于25帧。 入门知识&#xff1a; 1.帧&#xff0c;一张画面就是一帧。一个视频就是由许许多多帧组成的。 帧率&#xff0c;单位时间内帧的数量。单位&#xff1a;帧/秒 或 fps。 分类&#xff1a;I帧&#xff0c;P帧&#xff0c;B帧 I…
阅读更多...
IP协议报文

IP协议报文

一.IP协议报头结构 二.IP协议报头拆解 1.4位版本 实际上只有两个取值&#xff0c;分别是4和6&#xff0c;4代表的是IPv4&#xff0c;6代表的是IPv6。 2.4位首部长度 IP协议报头的长度也是边长的&#xff0c;单位是*4&#xff0c;这里表示的大小为0~15&#xff0c;当数值为1…
阅读更多...
【PyTorch】生成对抗网络

【PyTorch】生成对抗网络

生成对抗网络是什么 概念 Generative Adversarial Nets&#xff0c;简称GAN GAN&#xff1a;生成对抗网络 —— 一种可以生成特定分布数据的模型 《Generative Adversarial Nets》 Ian J Goodfellow-2014 GAN网络结构 Recent Progress on Generative Adversarial Networks …
阅读更多...
爬虫——同步与异步加载

爬虫——同步与异步加载

一、同步加载 同步模式--阻塞模式&#xff08;就是会阻止你浏览器的一个后续加载&#xff09;停止了后续的解析 因此停止了后续的文件加载&#xff08;图像&#xff09; 比如hifini音乐网站 二、异步加载 异步加载--xhr(重点) 比如腾讯新闻&#xff0c;腾讯招聘等 三、同…
阅读更多...
系统规划与管理——1信息系统综合知识（3）

系统规划与管理——1信息系统综合知识（3）

文章目录 1.3 信息系统1.3.1 信息系统定义1.3.2 信息系统的生命周期1.3.3 信息系统常用的开发方法 1.3 信息系统 1.3.1 信息系统定义 信息系统是一种以处理信息为目的的专门的系统类型。信息系统可以是手工的&#xff0c;也可以是计算机化的。计算机化的信息系统的组成部件包…
阅读更多...
【D3.js in Action 3 精译_025】3.4 让 D3 数据适应屏幕（中）—— 线性比例尺的用法

【D3.js in Action 3 精译_025】3.4 让 D3 数据适应屏幕（中）—— 线性比例尺的用法

当前内容所在位置&#xff08;可进入专栏查看其他译好的章节内容&#xff09; 第一部分 D3.js 基础知识 第一章 D3.js 简介&#xff08;已完结&#xff09; 1.1 何为 D3.js&#xff1f;1.2 D3 生态系统——入门须知1.3 数据可视化最佳实践&#xff08;上&#xff09;1.3 数据可…
阅读更多...
HTML:相关概念以及标签

HTML:相关概念以及标签

目录 什么是网页? 什么是HTML语言? 语法规范 HTML基本结构标签 DOCTYPE,lang以及字符集 HTML常用标签 5>图像标签(重要) 除此之外还有几个调整图片属性的标签 图像标签总结 什么是网页? 我们平时使用电脑和手机都是离不开网站和网页的,那么什么是网页呢?什么又是网…
阅读更多...
cocotb报错收集

cocotb报错收集

1、原因是定义测试类的时候&#xff0c;idle_inserter的名字不一样 函数修正后 函数修正前
阅读更多...
电脑显示mfc140u.dll丢失怎么办,分享4个有效的解决方法

电脑显示mfc140u.dll丢失怎么办,分享4个有效的解决方法

1. mfc140u.dll 简介 1.1 定义与作用 mfc140u.dll 是 Microsoft Foundation Class (MFC) 库中的一个动态链接库文件&#xff0c;它是 MFC 库在 Unicode 版本中的一个特定实现。MFC 是微软为 Windows 平台开发的一套 C 类库&#xff0c;封装了众多 Windows API 函数&#xff0…
阅读更多...
定时器定时中断定时器外部中断

定时器定时中断定时器外部中断

基础背景&#xff1a;TIM定时中断-CSDN博客 TIM的函数 // 恢复缺省设置 void TIM_DeInit(TIM_TypeDef* TIMx); // 时基单元初始化&#xff0c;第一个参数TIMx选择某个定时器&#xff0c;第二个参数是结构体&#xff0c;包含了配置时基单元的一些参数。 void TIM_TimeBaseInit…
阅读更多...
了解华为计算产品线，昇腾的业务都有哪些？

了解华为计算产品线，昇腾的业务都有哪些？

&#x1f349; CSDN 叶庭云&#xff1a;https://yetingyun.blog.csdn.net/ 随着 ChatGPT 的现象级爆红&#xff0c;它引领了 AI 大模型时代的深刻变革&#xff0c;进而造成 AI 算力资源日益紧缺。与此同时&#xff0c;中美贸易战的持续也使得 AI 算力国产化适配成为必然趋势。 …
阅读更多...
golang grpc初体验

golang grpc初体验

grpc 是一个高性能、开源和通用的 RPC 框架&#xff0c;面向服务端和移动端&#xff0c;基于 HTTP/2 设计。目前支持c、java和go&#xff0c;分别是grpc、grpc-java、grpc-go&#xff0c;目前c版本支持c、c、node.js、ruby、python、objective-c、php和c#。grpc官网 grpc-go P…
阅读更多...
Visual Studio 字体与主题推荐

Visual Studio 字体与主题推荐

个人推荐&#xff0c;仅供参考&#xff1a; 主题&#xff1a;One Monokai VS Theme 链接&#xff1a;One Monokai VS Theme - Visual Studio Marketplacehttps://marketplace.visualstudio.com/items?itemNameazemoh.onemonokai 效果&#xff1a; 字体&#xff1a;JetBrain…
阅读更多...
[RabbitMQ] Spring Boot整合RabbitMQ

[RabbitMQ] Spring Boot整合RabbitMQ

&#x1f338;个人主页:https://blog.csdn.net/2301_80050796?spm1000.2115.3001.5343 &#x1f3f5;️热门专栏: &#x1f9ca; Java基本语法(97平均质量分)https://blog.csdn.net/2301_80050796/category_12615970.html?spm1001.2014.3001.5482 &#x1f355; Collection与…
阅读更多...
Scrapy 爬虫的大模型支持

Scrapy 爬虫的大模型支持

使用 Scrapy 时&#xff0c;你可以轻松使用大型语言模型 (LLM) 来自动化或增强你的 Web 解析。 有多种使用 LLM 来帮助进行 Web 抓取的方法。在本指南中&#xff0c;我们将在每个页面上调用一个 LLM&#xff0c;从中抽取我们定义的一组属性&#xff0c;而无需编写任何选择器或…
阅读更多...
C++和OpenGL实现3D游戏编程【连载13】——多重纹理混合详解

C++和OpenGL实现3D游戏编程【连载13】——多重纹理混合详解

🔥C++和OpenGL实现3D游戏编程【目录】 1、本节要实现的内容 前面说过纹理贴图能够大幅提升游戏画面质量，但纹理贴图是没有叠加的。在一些游戏场景中，要求将非常不同的多个纹理（如泥泞的褐色地面、绿草植密布的地面、碎石遍布的地面）叠加（混合）起来显示，实现纹理间能够…
阅读更多...
多区域OSPF路由协议

多区域OSPF路由协议

前言 之前也有过关于OSPF路由协议的博客&#xff0c;但都不是很满意&#xff0c;不是很完整。现在也是听老师讲解完OSPF路由协议&#xff0c;感触良多&#xff0c;所以这里重新整理一遍。这次应该是会满意的 一些相关概念 链路状态 链路指路由器上的一个接口&#xff0c;链路状…
阅读更多...
YOLOv9最全详细翻译【人工校对版】

YOLOv9最全详细翻译【人工校对版】

阅读更多...
最新文章

Copyright @ 2022~2023