数据结构第六课 -----排序

作者前言

🎂 ✨✨✨✨✨✨🍧🍧🍧🍧🍧🍧🍧🎂
​🎂 作者介绍: 🎂🎂
🎂 🎉🎉🎉🎉🎉🎉🎉 🎂
🎂作者id:老秦包你会, 🎂
简单介绍:🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂
喜欢学习C语言和python等编程语言,是一位爱分享的博主,有兴趣的小可爱可以来互讨 🎂🎂🎂🎂🎂🎂🎂🎂
🎂个人主页::小小页面🎂
🎂gitee页面:秦大大🎂
🎂🎂🎂🎂🎂🎂🎂🎂
🎂 一个爱分享的小博主 欢迎小可爱们前来借鉴🎂


排序

  • **作者前言**
  • 直接插入排序
  • 冒泡排序
  • 希尔排序
  • 直接选择排序
  • 堆排序
  • 快速排序
      • hoare版本
    • 优化点
      • 三数取中
    • 小区间优化
    • 挖坑法
    • 前后指针版本
  • 疑惑

直接插入排序

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

思路: 我们要记得[0,end]是有序的,我们要把tmp的值插入到[0,end]就要进行判断,直到tmp等于数组的长度结束,这个过程中我们要注意到我们把tmp插入到[0,end] 是要遍历[0,end]的当我们判断当前的元素大于tmp,就把这个元素往后移动,我们就要往后一个元素比较,直到碰见比tmp小的元素,并再该元素后面插入,如果碰见了在[0,end]都没有小于tmp的元素,我们就要在下标为0的地方插入,

void InsertSort(int* a, int n)
{
	//[0,end] 
	int i = 0;
	for (i = 0; i < n-1; i++)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (a[end] > tmp)
			{
				//往后移动
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		//这个写法一箭双雕,一来可以防止end为-1的情况不用去判断,二来可以插入到a[end + 1]
		a[end + 1] = tmp;
	}
}

冒泡排序

在这里插入图片描述

// 冒泡排序
void Bubblisort(int* a, int n)
{
	int i = 0; 
	for (i = 0; i < n - 1; i++)
	{
		//如果该数组是一个有序数组,只需遍历一遍下面的就可以了,时间复杂度为O(N)
		bool excheng = false;
		int j = 0;
		for (j = 0; j < n - 1 - i; j++)
		{
			if (a[j] > a[j + 1])
			{
				int c = a[j];
				a[j] = a[j + 1];
				a[j + 1] = c;
				excheng = true;
			}
		}
		if (excheng == false)
			break;
	}
}

时间复杂度是O(N^2), 最好的情况就是O(N)

希尔排序

在这里插入图片描述

分成两步:
1.预排序 (接近有序)
2.直接插入排序
思路:
在这里插入图片描述
相同颜色的框进行插入排序,因为多少种颜色是有gap的数值决定的,每一种颜色对应的是整个数组的一部分

//预排序
	int gap = 3;
	int i = 0;
	//有gap个数组
	for (i = 0; i < gap; i++)
	{
		//每个数组进行插入排序
		int sub = i;
		while (sub <= n - 1 - gap)
		{
			int end = sub;
			int top = a[end + gap];
			while (end >= 0)
			{
				if (top < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
					break;
			}
			a[end + gap] = top;
			sub += gap;
		}
	}

上面这种是一组组进行插入排序.如果是多组进行插入排序

在这里插入图片描述
思路就是我们仍然采用上面的方法,但是我们是多组进行插入排序,仍然是相同颜色的进行插入排序

//预排序
	int gap = 3;
	int i = 0;
	//有gap个数组
	for (i = 0; i <= n - 1 - gap; i++)
	{
		//每个数进行插入排序
		
		int end = i;
		int top = a[end + gap];
		while (end >= 0)
		{
			if (top < a[end])
			{
				a[end + gap] = a[end];
				end -= gap;
			}
			else
				break;
		}
		a[end + gap] = top;
			
	}

预排序的特点:
gap越大,大的值更快调到后面,小的值可以更快的调到前面,越不接近有序
gap越小,跳得越慢,但是越接近有序,如果gap == 1就是直接插入排序

最终代码为

//希尔排序
void ShellSort(int* a, int n)
{
	//预排序
	int gap = 3;
	int i = 0;
	//有gap个数组
	for (i = 0; i <= n - 1 - gap; i++)
	{
		//每个数进行插入排序
		
		int end = i;
		int top = a[end + gap];
		while (end >= 0)
		{
			if (top < a[end])
			{
				a[end + gap] = a[end];
				end -= gap;
			}
			else
				break;
		}
		a[end + gap] = top;
			
	}
	//直接插入排序
	InsertSort(a, n);
}

但是我们可以简化一下
我们可以抓住gap=1为直接插入排序

//希尔排序
void ShellSort(int* a, int n)
{
	//预排序
	int gap = n;
	while (gap > 1)
	{
		//一来gap等于1时,就是直接插入排序,二来就是gap是随n增大的,
		//再还有就是gap越小,就越接近有序
		gap = gap / 3 + 1;
		int i = 0;
		//有gap个数组
		for (i = 0; i <= n - 1 - gap; i++)
		{
			//每个数进行插入排序

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

		}
	}
	
}

在这里插入图片描述
时间复杂度O(N ^1.3),这个有点难算,我们只需要理解大概就行

直接选择排序

在这里插入图片描述
思路:从开头开始找,找到最小的,然后进行和开头交换,然后再从剩下的后面继续寻找最小的,依次往后插入
思路图1:这个思路是很多人能想出来的

在这里插入图片描述
思路图2:

在这里插入图片描述

​这里我是使用了两边,左边插入最小的,右边插入最大的,插入好后,begin往前 ,end往后,直到begin等于end,就停止了

void excheng(int* a, int* b)
{
	int c = *a;
	*a = *b;
	*b = c;
}
//直接选择排序
void SelectSrot(int* a, int n)
{
	int min = 0, max = 0; //找出最大和最小
	int begin = 0, end = n - 1;// 在最大和最小的位置插入
	for (int i = begin + 1; i <= end; i++)
	{
		int idx = i;
		while (idx <= end)
		{
			//找出最小的值
			if (a[min] > a[idx])
				min = idx;
			//找到最大值
			if (a[max] < a[idx])
				max = idx;
			idx++;
		}
		excheng(&a[begin], &a[min]);
		//防止开头就是最大值,一旦最小值交换,就乱了
		if (max == begin)
			max = min;
		excheng(&a[end], &a[max]);
		begin++;
		end--;

	}
}

时间复杂度是 O(N^2)

堆排序

大家可以观看这部博客
堆排序
在这里插入图片描述

//堆排序
typedef int Heapdata;
void exchange(Heapdata* a, Heapdata* b)
{
	Heapdata e = *a;
	*a = *b;
	*b = e;
}
void Heapsort(Heapdata* heap, int size)
{
	//建大堆
	int i = 0;
	for (i = 1; i < size; i++)
	{
		//向上调整
		int child = i;
		int parent = (child - 1) / 2;
		while (child > 0)
		{
			if (heap[child] > heap[parent])
			{
				//交换
				exchange(&heap[child], &heap[parent]);
				child = parent;
				parent = (child - 1) / 2;
			}
			else
				break;
		}

	}
	//开始升序排序
	while (size > 0)
	{
		// 根节点和最后一个叶节点交换
		exchange(&heap[0], &heap[--size]);
		//向下调整
		int parent = 0;
		int child = parent * 2 + 1;
		while (child < size)
		{
			if (child + 1 < size && heap[child] < heap[child + 1])
			{
				child += 1;
			}
			if (heap[child] > heap[parent])
				exchange(&heap[child], &heap[parent]);
			else
				break;
			parent = child;
			child = parent * 2 + 1;
		}
	}



}

快速排序

hoare版本

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法,其基本思想为:任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止
在这里插入图片描述
这个图可能有点简陋
在这里插入图片描述
在这里插入图片描述
时间复杂度:每一次都会把当前数组的每个元素遍历一遍,然后再把key交换, 需要进行log(n)次递归
时间复杂度是:O(n*log(n))
在这里插入图片描述
复杂的话,就如同这个一样,这种情况就是有n层, 时间复杂度就是 1+2+3+…+n, 所以时间复杂度就是O(n^2)

//快速排序
void QuickSrot(int* a, int begin, int end)
{
	//当只有一个元素就不用进行了
	if (begin >= end)
		return;
	int key = begin;
	int left = begin;//这里不能begin加1 否则在遇到有序的时候就会排序出错
	int right = end;
	while (left < right)
	{
		// 找最小
		while (left < right)
		{
			if (a[right] < a[key])
			{
				break;
			}
			right--;
		}

		// 找最大
		while (left < right)
		{
			if (a[left] > a[key])
			{
				break;
			}
			left++;
		}
		
		excheng(&a[right], &a[left]);
	}
	excheng(&a[right], &a[key]);
	//左
	QuickSrot(a, begin, right - 1);
	// 右
	QuickSrot(a, right + 1, end);
}

优化点

三数取中

思路:
我们可以在数组的前后和中间选取中位数,然后把中位数和开头进行交换,

int TriNum(int *a,int begin, int end)
{
	int mid = (begin - end) / 2 + end;
	if (begin > end)
	{
		if (end > mid)
		{
			return end;
		}
		else if(begin < mid)
		{
			return begin;
		}
		return mid;
	}
	else
	{
		if (begin > mid)
		{
			return begin;
		}
		else if (end < mid)
		{
			return end;
		}
		else
			return mid;
	}
}
//快速排序
void QuickSrot(int* a, int begin, int end)
{
	//当只有一个元素就不用进行了
	if (begin >= end)
		return;
	//三数取中
	int key = 0;
	key = TriNum(a, begin, end);
	exchange(&a[begin], &a[key]);
	key = begin;
	int left = begin;
	int right = end;
	//普通方法
	//int key = begin;
	//int left = begin;//这里不能begin加1 否则在遇到有序的时候就会排序出错
	//int right = end;
	while (left < right)
	{
		// 找最小
		while (left < right)
		{
			if (a[right] < a[key])
			{
				break;
			}
			right--;
		}

		// 找最大
		while (left < right)
		{
			if (a[left] > a[key])
			{
				break;
			}
			left++;
		}
		
		excheng(&a[right], &a[left]);
	}

	excheng(&a[right], &a[key]);
	//左
	QuickSrot(a, begin, right - 1);
	// 右
	QuickSrot(a, right + 1, end);
}

小区间优化

当我们在使用快速排序的时候,一直排序知道递归到还剩下该数组的10%的数没有排序,我们如果使用递归就很对栈的空间浪费很大。那我们可以选择使用插入排序,

//快速排序
void QuickSrot(int* a, int begin, int end)
{
	//当只有一个元素就不用进行了
	if (begin >= end)
		return;
	if (end - begin  + 1 <= 10)
	{
		//插入排序
		InsertSort(a + begin, end - begin + 1);//我们要清楚要从哪里开始插入排序
	}
	else
	{
		//三数取中
		int key = 0;
		key = TriNum(a, begin, end);
		excheng(&a[begin], &a[key]);
		key = begin;
		int left = begin;
		int right = end;
		//普通方法,有可能会栈溢出
		//int key = begin;
		//int left = begin;//这里不能begin加1 否则在遇到有序的时候就会排序出错
		//int right = end;
		while (left < right)
		{
			// 找最小
			while (left < right)
			{
				if (a[right] < a[key])
				{
					break;
				}
				right--;
			}

			// 找最大
			while (left < right)
			{
				if (a[left] > a[key])
				{
					break;
				}
				left++;
			}

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

		excheng(&a[right], &a[key]);
		//左
		QuickSrot(a, begin, right - 1);
		// 右
		QuickSrot(a, right + 1, end);
	}
	
}

挖坑法

在这里插入图片描述

//挖坑法
void QuickSrot2(int* a, int begin, int end)
{
	if (begin >= end)
		return;
	if (end - begin + 1 <= 10)
	{
		InsertSort(a + begin, end - begin + 1);
	}
	else
	{
		//三数取中
		int key = TriNum(a, begin, end);
		excheng(&a[key], &a[begin]);
		//坑
		key = begin;
		int num = a[key];
		int left = begin;
		int right = end;
		while (left < right)
		{
			//找小
			while (left < right)
			{
				if (a[right] < num)
				{
					a[key] = a[right];
					key = right;
					break;
				}
				right--;
			}
			//找大
			while (left < right)
			{
				if (a[left] > num)
				{
					a[key] = a[left];
					key = left;
					break;
				}
				left++;
			}
		}
		a[key] = num;
		//左
		QuickSrot(a, begin, right - 1);
		// 右
		QuickSrot(a, right + 1, end);

	}
	
	

}

前后指针版本

在这里插入图片描述
思路:
cur遇见比key大的值,cur++
cur遇见比key小的值,prev++,交换prev和cur的值交换,然后cur++
在这里插入图片描述

//前后指针版本
// 快速排序版本3
void QuickSrot3(int* a, int begin, int end)
{
	if (begin >= end)
		return;
	int key = TriNum(a, begin, end);
	excheng(&a[key], &a[begin]);
	key = begin;
	int prev = begin;
	int cur = begin + 1;
	while (cur <= end)
	{
		//cur 比较
		if (a[cur] < a[key] && ++prev != cur)//增加++prev != cur可以有效解决相同位置进行交换
		{
			exchange(&a[cur], &a[prev]);
		}
		cur++;
	}
	exchange(&a[key], &a[prev]);
	//左
	QuickSrot(a, begin, prev - 1);
	// 右
	QuickSrot(a, prev + 1, end);
}

疑惑

在这里插入图片描述

  1. 为什么相遇位置比key小
    原因:是right先走
    两种情况:
    (1).R遇见L —>(L和R交换后,R先走)R没有找到比key小的,一直走,直到R遇见L,(特殊情况除外)
    (2)L遇见R----->(R找到小了),然后L没有找到比key大的,一直走,直到L遇见R,(特殊情况除外)

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

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

相关文章

Java开发环境详解(安装,工作流程,程序结构与终端运行)

参考书籍&#xff1a; 《明解Java》 《Java轻松学》 《Head First Java》 《Java核心技术卷I》 《Java核心技术卷II》 参考视频&#xff1a; Java零基础学习视频通俗易懂 Java入门基础视频教程&#xff0c;java零基础自学就选黑马程序员Java入门教程 参考网站&#xff1a; Kuan…

DNSLog漏洞探测(一)之DNSLog介绍

前言 DNSLog是一种基于DNS协议的信息收集技术,它可以用于网络安全领域的渗透测试、漏洞挖掘等方面。DNSLog的原理是利用DNS协议的特性,将需要收集的信息编码成DNS查询请求,然后将请求发送到DNS服务器,最后通过DNS服务器的响应来获取信息。DNSLog的实现方式有很多种,其中最常见…

.Net中的集合

所有的集合都是继承自IEnumerable。集合总体可以分为以下几类&#xff1a;关联/非关联型集合&#xff0c;顺序/随机访问集合&#xff0c;顺序/无序集合&#xff0c;泛型/非泛型集合&#xff0c;线程集合。 各集合类底层接口关系图 泛型与非泛型集合类的分析 泛型集合是类型安…

智能优化算法应用:基于入侵杂草算法3D无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用&#xff1a;基于入侵杂草算法3D无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用&#xff1a;基于入侵杂草算法3D无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.入侵杂草算法4.实验参数设定5.算法结果6.…

Qt之自定义QToolTip,去掉显示动画和隐藏延时

一.效果 先来看看Qt原生QToolTip的缺点: 1.当提示内容无变化时,弹窗无法移动。只能先传个空字符串强制弹窗隐藏,然后在新位置再传个字符串。 If the text is the same as the currently shown tooltip, the tip will not move. You can force moving by first hiding the t…

MIT18.06线性代数 笔记3

文章目录 对称矩阵及正定性复数矩阵和快速傅里叶变换正定矩阵和最小值相似矩阵和若尔当形奇异值分解线性变换及对应矩阵基变换和图像压缩单元检测3复习左右逆和伪逆期末复习 对称矩阵及正定性 特征值是实数特征向量垂直>标准正交 谱定理&#xff0c;主轴定理 为什么对称矩…

网上很火的记事软件有哪些?可以分类记事的工具选哪个

日常记事在生活及工作方面都是非常重要&#xff0c;选择好用的记事软件可以督促各项任务的按时完成&#xff0c;。随着科技的发展&#xff0c;越来越多的记事软件涌现出来&#xff0c;让人眼花缭乱。那么&#xff0c;网上很火的记事软件有哪些&#xff1f;可以分类记事的工具应…

Java服务占用过高CPU排除思路

一、背景说明 如果线上通过 java -jar xxx.jar 的方式启动的Java服务占用过高的CPU&#xff0c;我们通过top命令是可以查看到的。 那么问题来了&#xff0c;如果通过top命令查看到是因为java服务引起的占用过高的CPU时间&#xff0c;该如何进行排查呢&#xff1f; 二、排查思路…

【论文阅读】Reachability and distance queries via 2-hop labels

Cohen E, Halperin E, Kaplan H, et al. Reachability and distance queries via 2-hop labels[J]. SIAM Journal on Computing, 2003, 32(5): 1338-1355. Abstract 图中的可达性和距离查询是许多应用的基础&#xff0c;从地理导航系统到互联网路由。其中一些应用程序涉及到巨…

【模拟】LeetCode-48. 旋转图像

旋转图像。 给定一个 n n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。 你必须在 原地 旋转图像&#xff0c;这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。 示例 1&#xff1a; 输入&#xff1a;matrix [[1,2,3],[4,5,6]…

Python unittest单元测试框架 —— 断言assert !

assertEqual(a,b&#xff0c;[msg]):断言a和b是否相等&#xff0c;相等则测试用例通过。 assertNotEqual(a,b&#xff0c;[msg]):断言a和b是否相等&#xff0c;不相等则测试用例通过。 assertTrue(x&#xff0c;[msg])&#xff1a;断言x是否True&#xff0c;是True则测试用例…

现代雷达车载应用——第2章 汽车雷达系统原理 2.3节

经典著作&#xff0c;值得一读&#xff0c;英文原版下载链接【免费】ModernRadarforAutomotiveApplications资源-CSDN文库。 2.3 信号模型 雷达的发射机通常发出精心设计和定义明确的信号。然而&#xff0c;接收到的返回信号是多个分量的叠加&#xff0c;包括目标的反射、杂波…

Fiddler中AutoResponder的简单使用

AutoResponder&#xff0c;自动回复器&#xff0c;用于将 HTTP 请求重定向为指定的返回类型。 这个功能有点像是一个代理转发器&#xff0c;可以将某一请求的响应结果替换成指定的资源&#xff0c;可以是某个页面也可以是某个本地文件 1.使用 打开“Fiddler”&#xff0c;点击…

经典策略筛选-20231212

策略1&#xff1a; 龙头战法只做最强&#xff1a;国企改革 ----四川金顶 1、十日交易内出现 涨停或 &#xff08;涨幅大于7个点且量比大于3&#xff09; 2、JDK MACD RSI OBV BBI LWR MTM 六指标共振 3、均线多头 4、 筹码峰 &#xff08;锁仓&#xff09; 5、现价>…

用友 U8 Cloud upload.jsp 文件上传漏洞复现

0x01 产品简介 用友U8 Cloud 提供企业级云ERP整体解决方案,全面支持多组织业务协同,实现企业互联网资源连接。 U8 Cloud 亦是亚太地区成长型企业最广泛采用的云解决方案。 0x02 漏洞概述 用友U8 Cloud upload.jsp接口存在任意文件上传漏洞,攻击者可通过该漏洞上传木马,远…

网络基础(八):路由器的基本原理及配置

目录 1、路由概述 2、路由器 2.1路由器的工作原理 2.2路由器的转发原理 3、路由表 3.1路由表的概述 3.2路由表的形成 4、静态路由配置过程&#xff08;使用eNSP软件配置&#xff09; 4.1两个静态路由器配置过程 4.2三个静态路由器配置过程 5、默认路由配置过程 5.…

16、XSS——会话管理

文章目录 一、web会话管理概述1.1 会话管理1.2 为什么需要会话管理&#xff1f;1.3 常见的web应用会话管理的方式 二、会话管理方式2.1 基于server端的session的管理方式2.2 cookie-based的管理方式2.3 token-based的管理方式 三、安全问题 一、web会话管理概述 1.1 会话管理 …

智能优化算法应用:基于群居蜘蛛算法3D无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用&#xff1a;基于群居蜘蛛算法3D无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用&#xff1a;基于群居蜘蛛算法3D无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.群居蜘蛛算法4.实验参数设定5.算法结果6.…

智能优化算法应用:基于哈里斯鹰算法3D无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用&#xff1a;基于哈里斯鹰算法3D无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用&#xff1a;基于哈里斯鹰算法3D无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.哈里斯鹰算法4.实验参数设定5.算法结果6.…

C++_函数重载

前言&#xff1a; 函数重载的意思就是可以有多个同名函数存在&#xff0c;但是这些同名函数的参数列表有着不同情形&#xff0c;以便区分。在C中&#xff0c;支持在同一作用域下可以声明、定义多个同名函数&#xff0c;但是这些函数的形参类型&#xff0c;类型顺序以及参数个数…