【数据结构】排序（2）

目录

一、快速排序：

1、hoare(霍尔)版本：

2、挖坑法：

3、前后指针法：

4、非递归实现快速排序：

二、归并排序：

1、递归实现归并排序：

2、非递归实现归并排序： 

三、排序算法整体总结：

一、快速排序：

基本思想：

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

1、hoare(霍尔)版本：

运用递归原理，定义一个keyi（基准值），然后左找大，右找小，然后递归基准值的左右区间。 

具体思路：

  1. 选定一个基准值，可以是a[0] / a[Size-1]。
  2. 确定两个指针 left 和 right 分别从左边和右边向中间遍历数组。
  3. 例如：选最左边的为基准值则right先走，遇到比基准值大的就停下，然后left走，遇到比基准值小的就停下，然后交换left与right位置对应的值。（如果以最右边为基准值，则left先走，right后走）
  4. 重复以上步骤，直到left = right ，最后将基准值与left(right)位置的值交换。

这样下来基准值所在的位置就是它排序后正确所在的位置，因为左边的所有数都比他小，右边的所有数都比他大。

然后再递归以基准值为界限的左右两个区间中的数，当区间中没有元素时，排序完成。

代码实现：

// 三数选中位数返回下标，作为一个快排的小优化，(不用也可以，不影响后面的代码)
int GetMedian(int* a, int begin, int end)
{
	int midi = (begin + end) / 2;
	// begin end midi三个数选中位数
	if (a[begin] < a[midi])
	{
		if (a[midi] < a[end])
			return midi;
		else if (a[begin] > a[end])
			return begin;
		else
			return end;
	}
	else
	{
		if (a[end] > a[begin])
			return begin;
		else if (a[midi] > a[end])
			return midi;
		else
			return end;
	}
}

// hoare（霍尔）方法
int PartSort1(int* a, int begin, int end)// begin end 为下标
{
	int median = GetMedian(a, begin, end);// 选中位数返回下标

	swap(a[median], a[begin]); // 这里的swap使用的是库函数中写好了的，
                              // 使用自己写的注意形参与实参

	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]);
	}

	// 交换基准值和 left与right 交汇位置的值
	swap(a[left], a[keyi]);

	// 返回基准值的下标
	return left;
}

void QuickSort(int* a, int begin, int end) // begin end 为下标
{
	if (begin >= end)
	{
		return;
	}

	int keyi = PartSort1(a, begin, end);	

	// 继续递归keyi（已排好序的值）的左右区间
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

2、挖坑法：

具体思路：

  1. 从最左边选定一个基准值取出，然后这个位置就为“坑”。
  2. 还是运用左右指针，当右指针遇到比基准值小的值时，将该值放入坑中，然后右指针指向的位置就是新的“坑”，然后移动左指针，当左指针遇到比基准值大的值时，同样将该值放入坑中，然后左指针指向的位置就是新的“坑”，然后再移动右指针，以此反复直到左右指针相遇。
  3. 当左右指针相遇时，将基准值放入最后的“坑”中。

然后再递归以基准值为界限的左右两个区间中的数，当区间中没有元素时，排序完成。

 代码实现：

int PartSort1(int* a, int begin, int end)// begin end 为下标
{
	int median = GetMedian(a, begin, end);// 选中位数返回下标

	swap(a[median], a[begin]); // 这里的swap使用的是库函数中写好了的，
                              // 使用自己写的注意形参与实参

	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]);
	}

	// 交换基准值和 left与right 交汇位置的值
	swap(a[left], a[keyi]);

	// 返回基准值的下标
	return left;
}

// 挖坑法
int PartSort2(int* a, int begin, int end)
{
	int median = GetMedian(a, begin, end);// 选中位数返回下标

	swap(a[median], a[begin]); // 这里的swap使用的是库函数中写好了的，
	// 使用自己写的注意形参与实参

	// 定义基准值与“坑位”
	int keyi = a[begin];
	int hole = begin;

	// begin 与 end 充当左右指针
	while (begin < end)
	{
		// 右边找小，填到左边的坑
		while (begin < end && a[end] >= keyi)
		{
			end--;
		}

		// 填坑
		a[hole] = a[end];
		hole = end;

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

		// 填坑
		a[hole] = a[begin];
		hole = begin;
	}
	a[hole] = keyi;
	return hole;
}

void QuickSort(int* a, int begin, int end) // begin end 为下标
{
	if (begin >= end)
	{
		return;
	}

	int keyi = PartSort2(a, begin, end);	

	// 继续递归keyi（已排好序的值）的左右区间
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

3、前后指针法：

具体思路：

  1. 定义一个基准值key，指针 prev 和 cur。（cur = prev + 1）
  2. cur先走，遇到比key大的值，++cur。
  3. cur遇到比key小的值，++prev，交换prev和cur位置的值。
  4. 以此反复直到cur走出数组范围。

  5. 最后交换key和prev的值

然后再递归以基准值为界限的左右两个区间中的数，当区间中没有元素时，排序完成。

代码实现：

int PartSort3(int* a, int begin, int end)
{
	int median = GetMedian(a, begin, end);// 选中位数返回下标

	swap(a[median], a[begin]); // 这里的swap使用的是库函数中写好了的，
	// 使用自己写的注意形参与实参

	// 定义基准值、前后指针
	int keyi = begin;

	int prev = begin, cur = prev + 1;

	while (cur <= end)
	{
		// 保留keyi下标的值
		if (a[cur] < a[keyi] && ++prev != cur)// 避免自己给自己赋值的情况,
		{
			swap(a[prev], a[cur]);
		}
		++cur;
	}

	swap(a[prev], a[keyi]);

	// 因为交换了位置，所以下标prev的位置才是基准值
	return prev;
}

void QuickSort(int* a, int begin, int end) // begin end 为下标
{
	if (begin >= end)
	{
		return;
	}

	int keyi = PartSort3(a, begin, end);	

	// 继续递归keyi（已排好序的值）的左右区间
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

4、非递归实现快速排序：

非递归实现快速排序就需要运用到栈，栈中存放的是需要排序的左右区间。其大致思想是与递归实现的思路类似。

具体思路：

  1. 将待排序数组的左右下标入栈。
  2. 若栈不为空，分两次取出栈顶元素，分为闭区间的左右界限。
  3. 将区间中的元素按照【上述三种方法（霍尔、挖坑、前后指针）的任意一种】得到基准值的位置
  4. 再以基准值为界限，当基准值左右区间中有元素，将区间入栈

然后重复上述步骤直到栈中没有元素时，排序完成。

代码实现：

void QuickSortNonr(int* a, int begin, int end)
{
	// 这里使用的是C++标准模板库的stack，如果是C语言的话需手搓一个栈出来
	// 但基本的思路是一样的，这里为了方便就不手搓哩

	// 定义一个栈并初始化
	stack<int> s;

	// 将数组的左右下标入栈
	s.push(end);
	s.push(begin);

	// 当栈不为空时，继续排序
	while (!s.empty())
	{
		int left = s.top();
		s.pop();
		int right = s.top();
		s.pop();

		// 获取基准值的位置（下标）
		int keyi = PartSort1(a, left, right);
		// [left, keyi-1] keyi [keyi+1, right]

		// 以基准值为界限，若基准值左右区间中有元素，则将区间入栈
		if (left < keyi - 1)
		{
			s.push(keyi - 1);
			s.push(left);
		}

		if (keyi + 1 < right)
		{
			s.push(right);
			s.push(keyi + 1);
		}
	}
	// 如果是手搓的栈，记得释放内存
}

快速排序的特性总结：

  1. 快速排序整体的综合性能和使用场景都是比较好的。

  2. 时间复杂度：O(N*logN)

  3. 空间复杂度：O(logN)

  4. 稳定性：不稳定

二、归并排序：

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,采用分治法（Divide and Conquer）的一个非常典型的应用。 

基本思想：

将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

本质为：

依次将数组划分，直到每个序列中只有一个数字。一个数字默认有序，然后再依次合并排序。

1、递归实现归并排序：

代码实现：

void _MergeSort(int* a, int begin, int end, int* tmp)
{
	// 当区间中没有元素时将不再进行合并
	if (begin >= end)
	{
		return;
	}
	
	// 划分数组，进行递归操作
	int mid = (begin + end) / 2;
	
	_MergeSort(a, begin, mid, tmp);		// 划分左区间
	_MergeSort(a, mid + 1, end, tmp); // 划分右区间

	// 两个有序序列进行合并
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int i = begin;
	while (begin1 <= end1 && begin2 <= end2)// 结束条件为一个序列为空就停止。
	{
		if (a[begin1] < a[begin2])
		{
			tmp[i++] = a[begin1++];
		}
		else
		{
			tmp[i++] = a[begin2++];
		}
	}

	// 进行上一步的操作后会有一个有序序列不为空，将其合并进tmp
	while (begin1 <= end1)
	{
		tmp[i++] = a[begin1++];
	}

	while (begin2 <= end2)
	{
		tmp[i++] = a[begin2++];
	}

	//将合并后的序列拷贝到原数组中
	memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));

}

void MergeSort(int* a, int Size)
{
	//因为需要将两个有序序列进行合并，所以需要开辟相同空间
	int* tmp = (int*)malloc(sizeof(int) * Size);
	assert(tmp);

	_MergeSort(a, 0, Size - 1, tmp);
	free(tmp);
}

2、非递归实现归并排序： 

非递归实现的思想与递归实现的思想是类似的，但序列划分过程和递归是相反的，并不是每次一分为二， 而是先拆分为一个元素一组、再两个元素一组进行排序、再四个元素一组进行排序....以此类推，直到将所有的元素排序完。

代码实现：

void MergeSortNonR(int* a, int Size)
{
	int* tmp = (int*)malloc(sizeof(int) * Size);
	assert(tmp);

	// 先将元素拆为一个一组
	int gap = 1;
	while (gap < Size) // 当gap=Size时就是一组序列
	{
		// 每两组进行一个合并排序
		int index = 0; // 记录tmp数组中元素的下标
		for (int i = 0; i < Size; i += 2 * gap)// 两组中元素的个数为2*gap
		{
			// 控制两组的边界
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;

			// 当原数组中元素个数不是2^n时，最后两组会出现元素不匹配的情况

			// 情况1: 当 end1 >= Size 或 begin2 >= Size 时即最后两组元素只剩下一组时不需要进行合并排序
			if (end1 >= Size || begin2 >= Size)
			{
				break;
			}

			// 情况2: end2 >= Size 时，即最后两组中，第二组的元素个数小于第一组，则需要调整第二组的边界
			if (end2 >= Size)
			{
				end2 = Size - 1;
			}

			// 进行合并排序
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					tmp[index++] = a[begin1++];
				}
				else
				{
					tmp[index++] = a[begin2++];
				}
			}

			while (begin1 <= end1)
			{
				tmp[index++] = a[begin1++];
			}

			while (begin2 <= end2)
			{
				tmp[index++] = a[begin2++];
			}

			//一趟排序完后，将有序序列拷贝到原数组中
			memcpy(a, tmp, sizeof(int) * index);
		}

		// 更新gap变为二倍
		gap *= 2;
	}
	free(tmp);
	tmp = NULL;
}

归并排序的特性总结：

  1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
  2. 时间复杂度：O(N*logN)
  3. 空间复杂度：O(N)
  4. 稳定性：稳定

三、排序算法整体总结：

   稳定性：指数组中相同元素在排序后相对位置不发生变化。

 补充：

 1、在希尔排序中，增量的选择会影响其时间复杂度。

 2、序列初始顺序在一些算法中也会影响其时间复杂度。

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

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

相关文章

白酒：陈酿过程中的氧化还原反应与酒体老化

白酒：陈酿过程中的氧化还原反应与酒体老化

在云仓酒庄豪迈白酒的陈酿过程中&#xff0c;氧化还原反应与酒体老化是影响酒品质的重要因素。陈酿是白酒生产中不可或缺的一环&#xff0c;通过陈酿可以使酒体更加协调、口感更加醇厚。而氧化还原反应作为陈酿过程中的重要化学反应&#xff0c;对酒体的老化起着关键作用。 首先…
阅读更多...
Python列表：灵活多变的数据结构

Python列表：灵活多变的数据结构

文章目录 一、列表1.创建列表2.访问列表元素3.修改列表元素4.添加元素5.删除元素 二、列表脚本操作符1.连接运算符 2.重复运算符 * 三、列表函数&方法1.函数1.1 len() 函数1.2 max() 函数1.3 min() 函数1.4 sum() 函数1.5 list() 函数 2.方法2.1 append() 方法2.2 extend()…
阅读更多...
nginx 具体介绍

nginx 具体介绍

一&#xff0c;nginx 介绍 &#xff08;一&#xff09;nginx 与apache 1&#xff0c; Apache event 模型 相对于 prefork 模式 可以同时处理更多的请求 相对于 worker 模式 解决了keepalive场景下&#xff0c;长期被占用的线程的资源浪费问题 因为有监听线程&#…
阅读更多...
江科大STM32学习笔记（上）

江科大STM32学习笔记（上）

STM32F103xx 前言外设篇GPIO输出GPIO位结构GPIO模式外设的GPIO配置查看实战1&#xff1a; 如何进行基本的GPIO输入输出 OLED显示屏及调试Keil的调试模式演示 EXTI外部中断NVIC基本结构EXTI结构代码实战2&#xff1a;如何使用中断和对射式红外传感器&#xff06;旋转编码器 TIM&…
阅读更多...
嵌入式基础准备 | 初识嵌入式AI

嵌入式基础准备 | 初识嵌入式AI

1、嵌入式设备发展 1、第一代&#xff1a;2000年开始 单片机 最简单的电子产品 遥控器&#xff0c;烟雾报警器 裸机编程 RTOS 智能音箱&#xff0c;路由器&#xff0c;摄像头 实时性要求高的操作系统&#xff08;马上请求&#xff0c;马上响应&#xff09; 2、第二代&#xf…
阅读更多...
程序媛的mac修炼手册-- 小白入门Java篇

程序媛的mac修炼手册-- 小白入门Java篇

最近因为要用CiteSpace做文献综述&#xff0c;间接接触Java了。所以&#xff0c;继Python、C之后&#xff0c;又要涉猎Java了。刺激&#xff01;&#xff01; 由于CiteSpace与Java要求版本高度匹配&#xff0c;有个匹配详情明天为大家讲解。总之&#xff0c;我的Java之旅开始于…
阅读更多...
华清远见作业第四十一天——Qt（第三天）

华清远见作业第四十一天——Qt（第三天）

思维导图&#xff1a; 编程 完善对话框&#xff0c;点击登录对话框&#xff0c;如果账号和密码匹配&#xff0c;则弹出信息对话框&#xff0c;给出提示”登录成功“&#xff0c;提供一个Ok按钮&#xff0c;用户点击Ok后&#xff0c;关闭登录界面&#xff0c;跳转到其他界面 如…
阅读更多...
喜报 | 通付盾再次入选“苏州市网络和数据安全技术支撑单位”

喜报 | 通付盾再次入选“苏州市网络和数据安全技术支撑单位”

近日&#xff0c;为加强苏州市网络和数据安全技术服务体系建设&#xff0c;提升网络和数据安全保障水平&#xff0c;苏州市互联网信息办公室、苏州市互联网协会发布了2024-2025年度苏州市网络和数据安全技术支撑单位名单。经过自主申报、资料审核、专家评审等环节&#xff0c;江…
阅读更多...
「C语言进阶1」动态内存分配

「C语言进阶1」动态内存分配

目录 一、动态内存分配是什么&#xff1f; 二、为什么需要动态内存分配&#xff1f; 三、怎么进行动态内存分配&#xff1f; 1. malloc 2. calloc 3. realloc a. realloc功能解析 b. 内存泄漏和内存块被截断问题 c. 总结 4. free 四、使用动态内存分配常见的问题 【面试题】 一…
阅读更多...
线代：认识行列式、矩阵和向量

线代：认识行列式、矩阵和向量

本文主要参考的视频教程如下&#xff1a; 8小时学完线代【中国大学MOOC*小元老师】线性代数速学_哔哩哔哩_bilibili 另外这个视频可以作为补充&#xff1a; 【考研数学 线性代数 基础课】—全集_哔哩哔哩_bilibili 行列式的概念和定义 一般会由方程组来引出行列式 比如一个二阶…
阅读更多...
IO进程线程的通信操作

IO进程线程的通信操作

1.编程实现互斥机制 程序代码&#xff1a; 1 #include<myhead.h>2 int num520;//临界资源3 //1.创建一个互斥锁变量4 pthread_mutex_t mutex;//定义一个pthread_mutex_t类型的变量5 //定义任务1函数6 void *task1(void *arg)7 {8 printf("不畏过去\n");9 …
阅读更多...
java面试题之mybatis篇

java面试题之mybatis篇

什么是ORM&#xff1f; ORM&#xff08;Object/Relational Mapping&#xff09;即对象关系映射&#xff0c;是一种数据持久化技术。它在对象模型和关系型数据库直接建立起对应关系&#xff0c;并且提供一种机制&#xff0c;通过JavaBean对象去操作数据库表的数据。 MyBatis通过…
阅读更多...
驾校预约|驾校预约小程序|基于微信小程序的驾校预约平台设计与实现(源码+数据库+文档)

驾校预约|驾校预约小程序|基于微信小程序的驾校预约平台设计与实现(源码+数据库+文档)

驾校预约小程序目录 目录 基于微信小程序的驾校预约平台设计与实现 一、前言 二、系统功能设计 三、系统实现 1、用户​微信端功能模块​ 2、管理员服务端功能模块 &#xff08;1&#xff09;学员信息管理 &#xff08;2&#xff09; 教练信息管理 &#xff08;3&…
阅读更多...
Django学习笔记-HTML实现服务器图片的下载

Django学习笔记-HTML实现服务器图片的下载

1.index编写代码,跳转下载页面 2.创建download界面 3.编写download路由 4.创建download函数 1).如果请求的方法是GET&#xff0c;imglist变量存储从models.imgModel模型中获取的所有对象,创建字典ctx,使用render函数来渲染download.htm 2).如果请求的方法是POST,获取要下载的文…
阅读更多...
Spring学习上下文【ConfigurableApplicationContext】

Spring学习上下文【ConfigurableApplicationContext】

话不多说&#xff0c;先上图&#xff1a; ConfigurableApplicationContext是Spring框架中的一个接口&#xff0c;它继承了ApplicationContext接口&#xff0c;并扩展了一些额外的方法&#xff0c;用于允许应用程序在运行时动态地修改和管理应用上下文。ConfigurableApplicati…
阅读更多...
【js】无限虚拟列表的原理及实现

【js】无限虚拟列表的原理及实现

什么是虚拟列表 虚拟列表是长列表按需显示思路的一种实现&#xff0c;即虚拟列表是一种根据滚动容器元素的可视区域来渲染长列表数据中某一个部分数据的技术。 简而言之&#xff0c;虚拟列表指的就是「可视区域渲染」的列表。有三个概念需要了解一下&#xff1a; 视口容器元…
阅读更多...
KDD 2023 图神经网络方向论文总结

KDD 2023 图神经网络方向论文总结

ACM SIGKDD&#xff08;国际数据挖掘与知识发现大会&#xff0c;KDD&#xff09;是数据挖掘领域历史最悠久、规模最大的国际顶级学术会议&#xff0c;也是首个引入大数据、数据科学、预测分析、众包等概念的会议。今年&#xff0c;第29届 KDD 大会在美国加州长滩举行&#xff0…
阅读更多...
冒泡排序法的名字由来，排序步骤是什么，最坏情况下的排序次数如何计算得来的呢？

冒泡排序法的名字由来，排序步骤是什么，最坏情况下的排序次数如何计算得来的呢？

问题描述&#xff1a;冒泡排序法的名字由来&#xff0c;排序步骤是什么&#xff0c;最坏情况下的排序次数如何计算得来的呢&#xff1f; 问题解答&#xff1a; 冒泡排序法的名字来源于排序过程中较大的元素会像气泡一样逐渐“冒”到序列的顶端&#xff0c;而较小的元素则会逐…
阅读更多...
代码随想录算法训练营第四十天 343. 整数拆分、 96.不同的二叉搜索树

代码随想录算法训练营第四十天 343. 整数拆分、 96.不同的二叉搜索树

代码随想录算法训练营第四十天 | 343. 整数拆分、 96.不同的二叉搜索树 343. 整数拆分 题目链接&#xff1a;343. 整数拆分 - 力扣&#xff08;LeetCode&#xff09; 例如 n 10, 可以拆分为 3 * dp[7] 。因为dp[7]之前已经计算过最大 3 * 4&#xff0c; 所以dp[10] 3 * 3 …
阅读更多...
Microsoft 365自定义安装软件

Microsoft 365自定义安装软件

如图&#xff0c;在安装类型的步骤的时候&#xff0c;可以勾选自己想要的软件&#xff08;而非一股脑儿的安装一大堆自己不需要的&#xff09;。
阅读更多...
最新文章

Copyright @ 2022~2023