【数据结构】——排序篇(中)

前面我们已经了解了几大排序了,那么我们今天就来再了解一下剩下的快速排序法,这是一种非常经典的方法,时间复杂度是N*logN。

在这里插入图片描述

快速排序法:

基本思想为:任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止。

我们的快速排序可以通过递归和非递归来实现,我们先来看看递归实现快排,我们的递归快排又分为三个版本,三种方法各有各的特点,我们接下来就来看看吧。

需要调用的函数代码:

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

int GetMidi(int* a, int begin, int end)
{
	int midi = (begin + end) / 2;
	// begin midi end 三个数选中位数
	if (a[begin] < a[midi])
	{
		if (a[midi] < a[end])
			return midi;
		else if (a[begin] > a[end])
			return begin;
		else
			return end;
	}
	else // a[begin] > a[midi]
	{
		if (a[midi] > a[end])
			return midi;
		else if (a[begin] < a[end])
			return begin;
		else
			return end;
	}
}

hoare版本单趟排序:

// hoare
int PartSort1(int* a, int begin, int end)
{
	int midi = GetMidi(a, begin, end);
	Swap(&a[midi], &a[begin]);

	int left = begin, right = end;
	int keyi = begin;

	while (left < right)
	{
		// 右边找小
		while (left < right && a[right] >= a[keyi])
		{
			--right;
		}

		// 左边找大
		while (left < right && a[left] <= a[keyi])
		{
			++left;
		}

		Swap(&a[left], &a[right]);
	}

	Swap(&a[left], &a[keyi]);

	return left;
}

这个版本的单趟排序理解起来很容易,但是我们的坑点比较多,所以难度对于我们而言还是有点挑战性,我们需要两个变量来实现,我们的left从左边数组的首元素开始走,找比keyi位置大的元素,keyi代表的就是我们数组首元素的下标,我们用right从最后一个元素开始走,找比keyi位置小的元素,找到了一个大的元素和一个小的元素就交换,但是我们的数组中可能有多个相等的元素,所以我们内嵌循环就得用<=。我们最后left和right相遇时结束,相遇位置的右边的元素大于等于keyi位置的元素,而相遇位置左边的元素都小于等于keyi位置的元素,我们最后就将left位置的元素和keyi位置的元素交换再返回left就完成了。

挖坑法单趟排序:

int PartSort2(int* a, int begin, int end)
{
	int midi = GetMidi(a, begin, end);
	Swap(&a[midi], &a[begin]);

	int key = a[begin];
	int hole = begin;
	while (begin < end)
	{
		// 右边找小,填到左边的坑
		while (begin < end && a[end] >= key)
		{
			--end;
		}

		a[hole] = a[end];
		hole = end;

		// 左边找大,填到右边的坑
		while (begin < end && a[begin] <= key)
		{
			++begin;
		}

		a[hole] = a[begin];
		hole = begin;
	}

	a[hole] = key;
	return hole;
}

我们先将第一个数据存放在临时变量key中形成一个坑位,我们同样用到left和right,同样的用法,left从第一个元素往后走,right从最后一个元素往前走。我们的right先走,找到一个比hole下标小的元素就于hole下标的元素交换,交换之后left再走,找到一个比hole位置大的元素就与hole位置的元素交换,然后再left位置形成一个坑点。然后又是right走,交换后left走,反复进行,最后在相遇的时候就结束循环。因为我们的hole下标的值都是空的,所以在最后我们将key的数据给hole下标的坑位就可以了,最后再返回坑位的数据。具体的过程如下图所示:
在这里插入图片描述

前后指针版本单趟排序:

int PartSort3(int* a, int begin, int end)
{
	int midi = GetMidi(a, begin, end);
	Swap(&a[midi], &a[begin]);
	int keyi = begin;

	int prev = begin;
	int cur = prev + 1;
	while (cur <= end)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
			Swap(&a[prev], &a[cur]);

		++cur;
	}

	Swap(&a[prev], &a[keyi]);
	keyi = prev;
	return keyi;
}

我们的前后指针版本看起来比前两个版本更加的容易,因为我们的两个指针prev指向我们数组首元素的下标,而cur是我们首元素的下一个元素的下标,我们的cur先走,如果我们指向的元素比keyi位置的元素大的话我们就cur++向前走一位,如果比keyi位置的元素小的话我们就prev++向前走一位再与cur位置的交换,cur再继续往前走知道cur>end的时候就结束循环。最后我们再将prev位置的数据给keyi位置就完成了。
在这里插入图片描述

单趟优化版本:

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;

	if (end - begin + 1 <= 10)
	{
		InsertSort(a + begin, end - begin + 1);
	}
	else
	{
		int midi = GetMidi(a, begin, end);
		Swap(&a[midi], &a[begin]);

		int left = begin, right = end;
		int keyi = begin;

		while (left < right)
		{
			// 右边找小
			while (left < right && a[right] >= a[keyi])
			{
				--right;
			}

			// 左边找大
			while (left < right && a[left] <= a[keyi])
			{
				++left;
			}

			Swap(&a[left], &a[right]);
		}

		Swap(&a[left], &a[keyi]);
		keyi = left;

		// [begin, keyi-1] keyi [keyi+1, end]
		QuickSort(a, begin, keyi - 1);
		QuickSort(a, keyi + 1, end);
	}
}

单趟优化版本就是我们的区间数据不大时,我们用直接插入排序法,而数据太大的时候我们就用hoare版本的单趟排序。

函数递归实现快排:

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;

	int keyi = PartSort2(a, begin, end);
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

实现我们只需要调用一个版本的单趟排序在进行递归就可以了。我们代码中是用的挖坑法的单趟排序,我们就直接调用PartSort2就可以了。

递归的我们已经了解完了,那么我们就来看看非递归的怎么实现吧:

void QuickSortNonR(int* a, int begin, int end)
{
	ST s;
	STInit(&s);
	STPush(&s, end);
	STPush(&s, begin);

	while (!STEmpty(&s))
	{
		int left = STTop(&s);
		STPop(&s);
		int right = STTop(&s);
		STPop(&s);

		int keyi = PartSort3(a, left, right);
		// [left, keyi-1] keyi [keyi+1, right]
		if (left < keyi - 1)
		{
			STPush(&s, keyi - 1);
			STPush(&s, left);
		}

		if (keyi + 1 < right)
		{
			STPush(&s, right);
			STPush(&s, keyi + 1);
		}
	}

	STDestroy(&s);
}

非递归版本的快速排序。我们需要起始位置 begin 和结束位置 end。首先,函数创建一个栈 st,用于存储待处理的子数组的起始和结束位置。将 end 和 begin 分别压入栈中,表示对整个数组进行排序。进入循环,只要栈不为空,从栈中弹出两个元素,分别赋值给 left 和 right,表示当前要处理的子数组的起始和结束位置。调用 PartSort3 函数对子数组进行分区,得到基准元素的位置 keyi。根据分区的结果,将子数组划分为 [left, keyi-1]、[keyi]、[keyi+1, right] 三个部分。如果 keyi + 1 < right,说明右侧子数组仍然有元素需要排序,将右侧子数组的起始位置 keyi + 1 和结束位置 right 压入栈中。如果 left < keyi - 1,说明左侧子数组仍然有元素需要排序,将左侧子数组的起始位置 left 和结束位置 keyi - 1 压入栈中。循环继续进行,直到栈为空,表示所有子数组都被处理完毕。最后,销毁栈 st,就完成了非递归版本的快速排序。
在这里插入图片描述

如果对大家有所帮助的话就支持一下吧!

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

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

相关文章

自动驾驶学习笔记(十六)——目标跟踪

#Apollo开发者# 学习课程的传送门如下&#xff0c;当您也准备学习自动驾驶时&#xff0c;可以和我一同前往&#xff1a; 《自动驾驶新人之旅》免费课程—> 传送门 《Apollo 社区开发者圆桌会》免费报名—>传送门 文章目录 前言 匹配关联 轨迹记录 状态预测 总结 前…

C++使用策略模式,减少使用switch...case...

目录 原理函数类模板函数使用switch...case...不使用switch...case... 知识点decltypestd::remove_reference 原理 函数 #include <iostream> #include <functional> #include <map>void fun1(int a, int b) {std::cout << "fun1 : a "<…

uniApp项目的创建,运行到小程序

一、项目创建 1. 打开 HBuilder X 2. 右击侧边栏点击新建&#xff0c;选择项目 3. 填写项目名&#xff0c;点击创建即可 注&#xff1a;uniapp中如果使用生命周期钩子函数&#xff0c;建议使用哪种 ?(建议使用Vue的) 二、运行 1. 运行前先登录 2. 登录后点击 manifest.js…

Linux和Windows环境下如何使用gitee?

1. Linux 1.1 创建远程仓库 1.2 安装git sudo yum install -y git 1.3 克隆远程仓库到本地 git clone 地址 1.4 将文件添加到git的暂存区&#xff08;git三板斧之add&#xff09; git add 文件名 # 将指定文件添加到git的暂存区 git add . # 添加新文件和修改过的…

golang开发之个微机器人的二次开发

简要描述&#xff1a; 下载消息中的文件 请求URL&#xff1a; http://域名地址/getMsgFile 请求方式&#xff1a; POST 请求头Headers&#xff1a; Content-Type&#xff1a;application/jsonAuthorization&#xff1a;login接口返回 参数&#xff1a; 参数名必选类型…

测试用文章2

clion编辑器安装注意事项 clion是个非常优秀的cIDE&#xff0c;能大幅度提高我们写c的效率&#xff0c;最重要的是开箱即用。不过有些设置和注意事项&#xff0c;能让我们更好地使用clion 安装ideavim插件 vim插件&#xff0c;可以设置快捷键开启和关闭&#xff0c;推荐altf&am…

Windows下nginx的启动,重启,关闭等功能bat脚本

echo off rem 提供Windows下nginx的启动&#xff0c;重启&#xff0c;关闭功能echo begincls ::ngxin 所在的盘符 set NGINX_PATHG:::nginx 所在目录 set NGINX_DIRG:\projects\nginx-1.24.0\ color 0a TITLE Nginx 管理程序增强版CLSecho. echo. ** Nginx 管理程序 *** echo.…

文心ERNIE Bot SDK+LangChain:基于文档、网页的个性化问答系统

现在各行各业纷纷选择接入大模型&#xff0c;其中最火且可行性最高的形式无异于智能文档问答助手&#xff0c;而LangChain是其中主流技术实现工具&#xff0c;能够轻松让大语言模型与外部数据相结合&#xff0c;从而构建智能问答系统。ERNIE Bot SDK已接入文心大模型4.0能力&am…

平衡二叉树

AVL简称平衡二叉树&#xff0c;缩写为BBST&#xff0c;由苏联数学家 Adelse-Velskil 和 Landis 在 1962 年提出。 二叉树是动态查找的典范&#xff0c;但在极限情况下&#xff0c;二叉树的查找效果等同于链表&#xff0c;而平衡二叉树可以完美的达到 log ⁡ 2 n \log_2 n log2…

JVM 内存分析工具 Memory Analyzer Tool(MAT)的深度讲解

目录 一. 前言 二. MAT 使用场景及主要解决问题 三. MAT 基础概念 3.1. Heap Dump 3.2. Shallow Heap 3.3. Retained Set 3.4. Retained Heap 3.5. Dominator Tree 3.6. OQL 3.7. references 四. MAT 功能概述 4.1. 内存分布 4.2. 对象间依赖 4.3. 对象状态 4.4…

docker容器配置MySQL与远程连接设置(纯步骤)

以下为ubuntu20.04环境&#xff0c;默认已安装docker&#xff0c;没安装的网上随便找个教程就好了 拉去mysql镜像 docker pull mysql这样是默认拉取最新的版本latest 这样是指定版本拉取 docker pull mysql:5.7查看已安装的mysql镜像 docker images通过镜像生成容器 docke…

Git的安装以及SSH配置

前言 近期工作需要&#xff0c;所以版本管理工具要用到Git&#xff0c;某些操作需要ssh进行操作&#xff0c;在某次操作中遇到&#xff1a;git bash报错&#xff1a;Permission denied, please try again。经排查是ssh没有配置我的key&#xff0c;所以就借着这篇文章整理了一下…

典型的ETL使用场景

典型的ETL使用场景 ETL( Extract&#xff0c;Transform&#xff0c;Load)是一种用于数据集成和数据转换的常用技术。它主要用于从多个数据源中提取数据&#xff0c;对数据进行清洗、转换和整合&#xff0c;最后加载到目标系统中。ETL 的使用场景非常广泛&#xff0c;下面将介绍…

Windows系统Java开发环境安装

总结一下Java软件开发工程师常见的环境的安装&#xff0c;仅限Windows环境。 以下下载链接均来自官网&#xff0c;网络条件自己克服。 目录 1. JDKJDK Oracle 官网下载地址配置系统环境变量 2. Mavenapache maven 官网地址本地仓库和中央仓库配置配置系统环境变量 3. GitGit 官…

【Docker一】Docker架构、镜像操作和容器操作

一、docker基本管理和概念 1、概念 docker&#xff1a;开源的应用容器引擎。基于go语言开发的。运行在Linux系统中的开源的轻量级的“虚拟机” docker的容器技术可用在一台主机上轻松到达为任何应用创建一个轻量级到的&#xff0c;可移植的&#xff0c;自给自足的容器 dock…

二维码智慧门牌管理系统:提升管理效率

文章目录 前言一、快速准确录入&#xff1a;提高工作效率二、多样化支付&#xff1a;提供高效支付功能三、智能化管理&#xff1a;提高效率与准确性 前言 科技时代的必备工具 在当今科技高速发展的时代&#xff0c;二维码智慧门牌管理系统已成为各行业提高管理效率和准确性的重…

智能仪表板DevExpress Dashboard v23.1 - 支持自定义样式创建

使用DevExpress Analytics Dashboard&#xff0c;再选择合适的UI元素&#xff08;图表、数据透视表、数据卡、计量器、地图和网格&#xff09;&#xff0c;删除相应参数、值和序列的数据字段&#xff0c;就可以轻松地为执行主管和商业用户创建有洞察力、信息丰富的、跨平台和设…

C语言——字符函数和字符串函数(一)

&#x1f4dd;前言&#xff1a; 这篇文章对我最近学习的有关字符串的函数做一个总结和整理&#xff0c;主要讲解字符函数和字符串函数&#xff08;strlen&#xff0c;strcpy和strncpy&#xff0c;strcat和strncat&#xff09;的使用方法&#xff0c;使用场景和一些注意事项&…

gin投票项目5

对应视频V3版本 1.优化用户注册的功能 增加扩展字段 1.增加一个UUID字段&#xff0c;vachar&#xff08;50&#xff09;。 2.增加一个UUID的唯一索引。 UUID具有全局唯一性&#xff1b; 方法&#xff1a;在数据库中新建一个列&#xff0c;名为uuid并移至主键下方&#xf…

CRM系统选择技巧,什么样的CRM系统好用?

SaaS行业发展迅速&#xff0c;更多的企业逐渐选择CRM管理系统。打开搜索引擎&#xff0c;有非常多的结果。怎样在数十万个搜索结果中选择适合您的CRM系统&#xff1f;下面我们将聊聊&#xff0c;怎样选择CRM系统。 第一步&#xff1a;明确自身需求 重要性&#xff1a;每家企业…