排序大乱炖

目录

一：插入排序

1.1直接插入排序

1.2希尔排序

二：选择排序

2.1选择排序

2.2堆排序

三：交换排序

3.1冒泡排序

3.2快速排序 

3.2.1Hoare版本

3.2.2双指针法 

3.2.3非递归 

一：插入排序

1.1直接插入排序

直接插入排序，可以有很多种写法，写法也比较简单，在这里，我主要介绍一种和希尔排序十分相似的思想，方便后续讲解希尔排序

在这里我们定义一个变量end，它用来记录下标，在这里我们认为[0,end]范围内的数组是有序的，然后将下标end+1所在的数组，与[0,end]范围内的数组比大小（所有排序讲解的均为升序），放在合适的位置 。

如果，a[end] > a[end+1]，我们即将a[end]的数字，放在end+1处，这是又会产生一个问题，我们是每次比较都要两个数字交换，还是让a[end]直接将a[end+1]覆盖呢？

直接覆盖肯定是首先就排除的，因为覆盖会使数据缺失，那就选每次比价，每次交换吗？

但是，如果数组长度很长，可能依次交换，并不能让a[end+1]放在合适的位置，这样看每次交换可能不如直接覆盖来的快，这时我们可以取一个折中的方法：在新建一个变量tmp，将a[end+1]的值存在tmp，让后直接覆盖就可以了，但是tmp不着急让在end处，我们将继续比较，找到正确的位置直接将tmp放入即可

由上图，可以写出代码：

//插入排序
//直接插入排序
void InsertSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		//单趟,[0,end]为有序数组，将a[end+1]插入数组
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}

		a[end + 1] = tmp;
	}
	
}

1.2希尔排序

希尔排序通过名字可以看出是一个名叫希尔的大佬创造的方法，而当时这位大佬在写这个代码的时候正是想通过自己的方法，改良直接插入排序，所以希尔排序的思想和上面的直接插入排序很相似。

希尔排序和直接插入排序相比所做出的优化就是，先进行预排序，让数组十分接近有序，在进行一次插入排序即可。

预排序，就是将间隔gap的数分为一组，在这一小组中先进行排序，排完这几个小组后，再将gap变小，继续进行进行预排序，随着gap的减少，每一小组的成员不断增加，知道gap减少到1，也就是直接插入排序，之后数组有序

控制一组颜色排序：

    for (int i = 0; i < n - gap; i+= gap)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}

排完一种颜色，再排下一组颜色，知道所有组排完，一趟排序结束

for(int j = 0; j< gap; j++)
{
    for (int i = j; i < n - gap; i++)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
}

此时此刻，我们排完一趟排序，已经用了三个循环，这样想，你是否觉得时间复杂度已经爆了呢？但是在数据十分庞大时，希尔排序也即是说比快排慢一点而已，所以大佬之所被称为大佬不是没有原因的。各位，请继续往下看，静等希尔排序的奇迹！

其实，前面排完一趟是，希尔当时的原版本，在这之后还有大佬，对这一段代码，进行了优化，时间复杂度并没有变化，只是代码更简洁一点用了两个循环。

思路，排每一组的第一个，然后第一个都排完以后，再同时排第二个

    for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}

排完一趟以后，在最外面，再套上一层循环控制gap即可

//希尔排序
//预排序：接近有序
//直接排序：gap == 1，插入排序
void ShellSort(int* a, int n)
{
	int gap = n;

	while (gap > 1)
	{ 
		gap = gap / 3 + 1;//最后一次是1
		//先排每一组的第一个，排完以后依次类推
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
	
}

对于gap的取值，希尔的初始版本是gap /= 2,这样就可以保证gap最后一次是1

后来，又有人经过大量实验数据得出，gap模3时，效率最高，但是/3的最后结果可能是0，所以为了保证最后一次是0，gap = gap/3+1

二：选择排序

2.1选择排序

选择排序就十分简单粗暴，即使遍历一遍数组，选出最小的，然后让最小的与下标为0的数字互换，然后重复

再这里可以做一点小小的优化就是一次选出最大和最小

//选择排序
//选择排序
void SelectSort(int* a, int n)
{
	int begin = 0, end = n - 1;
	while (begin < end)
	{
		int mini = begin, maxi = begin;
		for (int i = begin + 1; i <= end; i++)
		{
			if (a[i] < a[mini])
				mini = i;

			if (a[i] > a[maxi])
				maxi = i;
		}
		Swap(&a[begin], &a[mini]);

		//如果maxi和bgein重合，前面begin和mini换了值以后，最大的数应该在mini下标
		if (begin == maxi)
			maxi = mini;

		Swap(&a[end], &a[maxi]);

		end--;
		begin++;
	}

2.2堆排序

堆排序分为两个部分就是建堆和排序

建堆：由于升序建大堆

//向下调整
void AdjustDown(int* a, int parent, int n)
{
	int child = parent * 2 + 1;

	while (child < n)
	{
		if (child + 1 < n && a[child + 1] > a[child])
		{
			++child;
		}

		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);

			parent = child;
			child = parent *2+ 1;
		}
		else
		{
			break;
		}
	}
}

//堆排序
void HeapSort(int* a, int n)
{
	//建堆:升序见大堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
	AdjustDown(a, i , n);
	}

	//排序
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);

		AdjustDown(a, 0, end);
		end--;
	}
}

三：交换排序

3.1冒泡排序

冒泡排序就是将数组遍历一遍，建最大的数字冒到最后，然后最后一个位置不参与遍历，在从头开始遍历，找到次大的

代码如下：

//交换排序
//冒泡排序
void BubbleSort(int* a, int n)
{
	for (int j = 0; j < n - 1; j++)
	{
		for (int i = 0; i < n - 1-j; i++)
		{
			if (a[i] > a[i + 1])
			{
				Swap(&a[i], &a[i + 1]);
			}
		}
	}
	
}

3.2快速排序 

3.2.1Hoare版本

对于单趟排序，根据上面位置，很多人会写出这样的单趟排序

        int key = a[left];
		while (left < right)
		{
			//右边先走，找小
			//还要保证在数组范围内
			while (left < right && a[right] > key)
			{
				right--;
			}

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

			//此时left所在的位置大于key，right所在的位置小于key
			Swap(&a[left], &a[right]);
		}
		//此时left和right相遇
		Swap(&key, &a[left]);

 此时，如果调试一下，会发现最后交换时，数组第一个值并没有变，因为创建了一个变量key，用来存最左边的值，相当于创建了一个临时变量，所以最后交换时，是临时变量，与数组中的值交换的，所以我们可以创建一个变量，用于存下标

解决了这个问题，循环条件，还有一个隐藏的条件，如果是以下数组，left和right如何呢？

单趟排序的代码：

        int keyi = left;
		while (left < right)
		{
			//右边先走，找小
			//还要保证在数组范围内
			while (left < right && a[right] > a[keyi])
			{
				right--;
			}

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

			//此时left所在的位置大于key，right所在的位置小于key
			Swap(&a[left], &a[right]);
		}
		//此时left和right相遇
		Swap(&a[keyi], &a[left]);
		keyi = left;

排完单趟以后，就是排整个数组，也就是递归，递推

完整的排序代码：

        if (left >= right)
        		return;        
         //单趟
		int begin = left, end = right;
        int keyi = left;
		while (left < right)
		{
			//右边先走，找小
			//还要保证在数组范围内
			while (left < right && a[right] > a[keyi])
			{
				right--;
			}

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

			//此时left所在的位置大于key，right所在的位置小于key
			Swap(&a[left], &a[right]);
		}
		//此时left和right相遇
		Swap(&a[keyi], &a[left]);
		keyi = left;

		//[begin,keyi -1] keyi [keyi+1,end]
		//递归
		PartSort1(a, begin, keyi - 1);
		PartSort1(a, keyi + 1, end);

以上是最基础的快排，但是在厉害的排序也是有自己的不足的，基础版的快排有一个不足就是，如果数组是顺序时，时间复杂度就会从n*logn变成n^2

这个问题会出现是因为我们每次都选择最左边的值作为key,为了解决这个问题，大佬们分别有不同的解决方法，比较常用的是随机值和三数取中 

随机值法：顾名思义就是让key是个随机数，不再让key固定即使key，而为了让我们单趟写的代码不发生太大的变化，我们可以选出这个之后，再让这个值与left位置的值互换，这样代码处的left就可以继续使用了


		//单趟
		int begin = left, end = right;

		//随机选取keyi
		int randi = rand() % (right - left);
		randi += left;
		Swap(&a[randi], &a[left]);

		int midi = GetMid(a, left, right);
		Swap(&a[midi], &a[left]);

		int keyi = left;
		while (left < right)
		{
			//右边先走，找小
			//还要保证在数组范围内
			while (left < right && a[right] >= a[keyi])
			{
				right--;
			}

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

			//此时left所在的位置大于key，right所在的位置小于key
			Swap(&a[left], &a[right]);
		}
		//此时left和right相遇
		Swap(&a[keyi], &a[left]);
		keyi = left;

		//[begin,keyi -1] keyi [keyi+1,end]
		//递归
		PartSort1(a, begin, keyi - 1);
		PartSort1(a, keyi + 1, end);

三数取中：三数取中并不是取下标的中间值，而是取下标处的数组值的中间值，三数取中应用有序数组可以将复杂度再拉回n*logn

//三数取中
int GetMid(int* a, int left, int right)
{
	int midi = (left + right) / 2;

	if (a[left] > a[midi])
	{
		if (a[midi] > a[right])
			return midi;

		//a[midi] 最小
		else if (a[left] < a[right])
			return left;

		else
			return right;
	}
	else//a[left] < a[midi]
	{
		if (a[midi] < a[right])
			return midi;

		//a[midi]最大
		else if (a[left] > a[right])
			return left;

		else
			return right;
	}
}

而有的大佬，为了让快排更快，有做出了一些优化

递归过程，越往下所占总体比例越大 ，和二叉树类似，最后一层就占总体的50%，而且越往下数组区间越小，因此下面区间小的数组就不值得再往下递归了，之间排序了，一般当数组区间小于10时，就用插入排序

// 快速排序hoare版本

//三数取中
int GetMid(int* a, int left, int right)
{
	int midi = (left + right) / 2;

	if (a[left] > a[midi])
	{
		if (a[midi] > a[right])
			return midi;

		//a[midi] 最小
		else if (a[left] < a[right])
			return left;

		else
			return right;
	}
	else//a[left] < a[midi]
	{
		if (a[midi] < a[right])
			return midi;

		//a[midi]最大
		else if (a[left] > a[right])
			return left;

		else
			return right;
	}
}
void  PartSort1(int* a, int left, int right)
{
	if (left >= right)
		return;
	
	if (right - left + 1 < 10)
	{
		InsertSort(a, right - left + 1);
	}
	else
	{
		//单趟
		int begin = left, end = right;

		//随机选取keyi
		//int randi = rand() % (right - left);
		//randi += left;
		//Swap(&a[randi], &a[left]);

		int midi = GetMid(a, left, right);
		Swap(&a[midi], &a[left]);

		int keyi = left;
		while (left < right)
		{
			//右边先走，找小
			//还要保证在数组范围内
			while (left < right && a[right] >= a[keyi])
			{
				right--;
			}

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

			//此时left所在的位置大于key，right所在的位置小于key
			Swap(&a[left], &a[right]);
		}
		//此时left和right相遇
		Swap(&a[keyi], &a[left]);
		keyi = left;

		//[begin,keyi -1] keyi [keyi+1,end]
		//递归
		PartSort1(a, begin, keyi - 1);
		PartSort1(a, keyi + 1, end);
	}
}

3.2.2双指针法 

 除了Hoare原本的版本以外，还有用双指针法来写快排

代码：

/ 快速排序前后指针法
void  PartSort3(int* a, int left, int right)
{
	if (left >= right)
		return;

	
	int begin = left, end = right;

	int midi = GetMid(a, left, right);
	Swap(&a[midi], &a[left]);

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

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

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

3.2.3非递归 

快排不一定必须要用递归，也可以借助栈来实现

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

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

相关文章

ESCTF赛题WP

ESCTF赛题WP

ESCTF_reverse题解 逆吧腻吧babypybabypolyreeasy_rere1你是个好孩子完结撒花 Q_W_Q 逆吧腻吧 下载副本后无壳&#xff0c;直接拖入ida分析分析函数逻辑&#xff1a;ida打开如下&#xff1a;提取出全局变量res的数据后&#xff0c;编写异或脚本进行解密&#xff1a; a[0xBF, …
阅读更多...
技术与业务：项目成功的黄金关键

技术与业务：项目成功的黄金关键

目录 前言1 明确业务需求2 技术选择与业务匹配3 解决方案设计与业务一致4 开发与实施5 持续监控与优化6 反馈循环与持续改进结语 前言 在当今数字化时代&#xff0c;技术与业务之间的紧密联系对于项目的成功至关重要。无论是开发新产品、提供服务还是改进现有流程&#xff0c;…
阅读更多...
Avalonia(11.0.2)+.NET6 打包设置发布包的版本号

Avalonia(11.0.2)+.NET6 打包设置发布包的版本号

Avalonia11.0.2+.NET6 打包设置发布包的版本号 系统版本如何打包设置打包的版本号本文是对上一篇打包文章的补充，后台好多人私信我说打包的版本号如何设置，今天出个补充说明 Avalonia(11.0.2)+.NET6 打包运行到银河麒麟V10桌面系统 系统版本 如何打包 Avalonia(11.0.2)+.NET…
阅读更多...
基于nodejs+vue宿舍管理系统python-flask-django-php

基于nodejs+vue宿舍管理系统python-flask-django-php

随着信息时代的来临&#xff0c;过去的传统管理方式缺点逐渐暴露&#xff0c;对过去的传统管理方式的缺点进行分析&#xff0c;采取计算机方式构建宿舍管理系统。本文通过课题背景、课题目的及意义相关技术&#xff0c;提出了一种楼宇信息、宿舍信息、宿舍安排、缺勤信息等于一…
阅读更多...
职场口才提升之道

职场口才提升之道

职场口才提升之道 在职场中&#xff0c;口才的重要性不言而喻。无论是与同事沟通协作&#xff0c;还是向上级汇报工作&#xff0c;亦或是与客户洽谈业务&#xff0c;都需要具备良好的口才能力。一个出色的职场人&#xff0c;除了拥有扎实的专业技能外&#xff0c;还应具备出色…
阅读更多...
赚钱的四条途径：信息、认知、执行力与竞争力的差异

赚钱的四条途径：信息、认知、执行力与竞争力的差异

一、引言 在追求财富的道路上&#xff0c;每个人都希望能够找到一条通往成功的捷径。事实上&#xff0c;赚钱的途径并非神秘莫测&#xff0c;而是由一系列关键因素所构成。其中&#xff0c;信息相差、认知相差、执行力相差以及竞争力相差&#xff0c;是赚钱的四条重要途径。这…
阅读更多...
吴恩达2022机器学习专项课程(一） 第一周课程实验：模型表示（Lab_03）

吴恩达2022机器学习专项课程(一） 第一周课程实验：模型表示（Lab_03）

目标 学习如何使用一个变量实现线性回归模型。 导入需要的库 存储特征x和目标变量y 这是真实的训练集&#xff0c;[1.0,2.0]是房子的大小&#xff0c;[300,500]是房子的价格。 使用数组存储训练集的数据&#xff1a; x_train&#xff1a;存储的是所有特征&#xff0c;[1.…
阅读更多...
hyperf 二十八 修改器 一

hyperf 二十八 修改器 一

教程&#xff1a;Hyperf 一 修改器和访问器 根据教程&#xff0c;可设置相关函数,如set属性名Attribute()、get属性名Attribute()&#xff0c;设置和获取属性。这在thinkphp中也常见。 修改器&#xff1a;set属性名Attribute()&#xff1b;访问器&#xff1a;get属性名Attri…
阅读更多...
【mysql基础知识】

【mysql基础知识】

mysql数据类型 MySQL数据类型定义了数据的大小范围&#xff0c;因此使用时选择合适的类型&#xff0c;不仅会降低表占用的磁盘空间&#xff0c; 间接减少了磁盘I/O的次数&#xff0c;提高了表的访问效率&#xff0c;而且索引的效率也和数据的类型息息相关。 数值类型 比如说…
阅读更多...
某蓝队面试经验

某蓝队面试经验

背景 据小道消息说今年的国护疑似提前到了五月份&#xff0c;所以最近也是HW面试的一个高峰期啊&#xff0c;这里分享一下上次长亭的蓝队面试问题&#xff08;附本人的回答&#xff0c;仅供参考&#xff09; 面试问答 1、谈谈作为蓝队护网过程使用过厂商的设备 这里我回答的…
阅读更多...
1424:喷水装置——1425:加工生产调度【贪心之区间问题和流水调度问题】

1424:喷水装置——1425:加工生产调度【贪心之区间问题和流水调度问题】

1424：【例题3】喷水装置 时间限制: 1000 ms 内存限制: 65536 KB 【题目描述】 长 L 米，宽 W 米的草坪里装有 n 个浇灌喷头。每个喷头都装在草坪中心线上（离两边各 W2 米）。我们知道每个喷头的位置（离草坪中心线左端的距离），以及它能覆盖到的浇灌范围。 请问：如…
阅读更多...
车道线检测中的IPM变换

车道线检测中的IPM变换

车道线检测中的IPM变换 车道线检测(Lane Detection)是 ADAS 系统中重要的功能模块&#xff0c;而对于 L4 自动驾驶系统来说&#xff0c;在不完全依赖高精度地图的情况下&#xff0c;车道线检测结果也是车辆运动规划的重要输入信息。由于俯视图(BEV, Bird’s Eye View)下做车道…
阅读更多...
【Tanshtech】生物膜/细胞膜包裹纳米颗粒CMNs递送药物定制

【Tanshtech】生物膜/细胞膜包裹纳米颗粒CMNs递送药物定制

细胞膜包裹的纳米颗粒&#xff08;Cell membrane-coated nanoparticles&#xff0c;CNPs&#xff09;是一类新兴的纳米载体&#xff0c;其通过天然细胞膜将纳米颗粒包裹在核心位置&#xff0c;使得它们能够在复杂的生物体环境中逃逸免疫清除&#xff0c;并在靶定肿瘤部位积累。…
阅读更多...
城市内涝水文水动力模型：慧天【HTWATER】

城市内涝水文水动力模型：慧天【HTWATER】

查看详情>>> 城市内涝水文水动力模型&#xff1a;慧天【HTWATER】 【城市内涝水文水动力模型介绍】 慧天排水数字化分析平台针对城市排水系统基础设施数据管理的需求&#xff0c;以及水文、水力及水质模拟对数据的需求&#xff0c;实现了以数据库方式对相应数据的存…
阅读更多...
python笔记（2）基础语法

python笔记（2）基础语法

python 保留字 import keyword print(keyword.kwlist)运行 "Import-Module PSReadLine"。PS F:\学习\python\测试> & C:/Users/Python/Python311/python.exe f:/学习/python/测试/test.py [False, None, True, and, as, assert, async, await, break, class,…
阅读更多...
九泰智库 | 医械周刊- Vol.17

九泰智库 | 医械周刊- Vol.17

⚖️ 法规动态 器审中心公示新一期医疗器械优先审批申请审核结果 3月22日&#xff0c;依据原国家食品药品监督管理总局《医疗器械优先审批程序》&#xff08;总局公告2016年168号&#xff09;&#xff0c;器审中心对申请优先审批的医疗器械注册申请进行了审核&#xff0c;对相关…
阅读更多...
优化登录页面

优化登录页面

作业&#xff1a; 完善对话框&#xff0c;点击登录对话框&#xff0c; 如果账号和密码匹配&#xff0c;则弹出信息对话框&#xff0c;给出提示”登录成功“&#xff0c;提供一个0k按钮&#xff0c;用户点击Ok后&#xff0c;关闭登录界面&#xff0c;跳转到其他界面如果账号和密…
阅读更多...
java常用应用程序编程接口（API）——IO流概述及字节流的使用

java常用应用程序编程接口（API）——IO流概述及字节流的使用

前言&#xff1a; IO流和File是用于把数据存放在硬盘里的工具。File可以把文件存至硬盘&#xff0c;但不能更改里面的数据。通过IO流可以改写硬盘里的数据。整理下学习笔记&#xff0c;打好基础&#xff0c;daydayup!!! IO流 I指Input&#xff0c;称为输入流&#xff1a;负责把…
阅读更多...
1_88. 合并两个有序数组

1_88. 合并两个有序数组

1_88. 合并两个有序数组 难度: 简单 提示: 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2&#xff0c;另有两个整数 m 和 n &#xff0c;分别表示 nums1 和 nums2 中的元素数目。请你合并 nums2 到 nums1 中&#xff0c;使合并后的数组同样按 非递减顺序 排列。 注意…
阅读更多...
Qt登录页面

Qt登录页面

#include "mywidget.h" #include "ui_mywidget.h"MyWidget::MyWidget(QWidget *parent): QWidget(parent), ui(new Ui::MyWidget) {ui->setupUi(this);//接收动图QMovie *mv new QMovie(":/pictrue/luori.gif");ui->loglab->setMovie(…
阅读更多...
最新文章

Copyright @ 2022~2023