数据结构学习笔记——选择排序（简单选择排序和堆排序）

news/2024/5/19 4:06:26 标签: 数据结构, 排序算法, 堆排序, 选择排序, 算法

目录

一、简单选择排序

（一）排序思想

以递增为例，在每一趟的简单选择排序过程中，每次选取当前元素最小的元素，将其作为有序子序列的第i，i+1，……个元素，依次进行下去，即和第一个元素交换，依次进行交换，直到剩余一个元素，此时整个序列已经有序，每一趟简单选择排序可确定一个元素的最终位置。
递增的简单选择排序代码如下：

/*简单选择排序（递增）*/
void SelectSort1(int r[],int n) {
	int i,j,min,temp;
	for(i=0; i<n-1; i++) {	//for循环进行n-1趟 
		min=i;	//min变量记录最小元素的位置 
		for(j=i+1; j<n; j++) {	//从无序序列中选择一个最小的元素 
			if(r[j]<r[min])	
				min=j;
		}	 
		temp=r[i];	//将最小元素与无序序列的第一个关键字进行交换
		r[i]=r[min];
		r[min]=temp;
	}
}

同样，递减的简单选择排序代码如下：

/*简单选择排序（递减）*/
void SelectSort2(int r[],int n) {
	int i,j,max,temp;
	for(i=0; i<n-1; i++) {	//for循环进行n-1趟 
		max=i;	//max变量记录最小元素的位置 
		for(j=i+1; j<n; j++) {	//从无序序列中选择一个最大的元素
			if(r[j]>r[max])
				max=j;
		}	
		temp=r[i];	//将最大元素与无序序列的第一个关键字进行交换 
		r[i]=r[max];
		r[max]=temp;
	}
}

例如，对于一个序列{-2，0，7，1，4，3}进行简单选择排序，输出其递增和递减序列，代码如下：

#include<stdio.h>
#define MAXSIZE 100
/*创建函数*/
void Create(int r[],int n) {
	for(int i=0; i<n; i++) {
		printf("输入第%d个元素：",i+1);
		scanf("%d",&r[i]);
	}
}

/*输出函数*/
void Display(int r[],int n) {
	for(int i=0; i<n; i++)
		printf("%d ",r[i]);
}

/*简单选择排序（递增）*/
void SelectSort1(int r[],int n) {
	int i,j,min,temp;
	for(i=0; i<n-1; i++) {	//for循环进行n-1趟 
		min=i;	//min变量记录最小元素的位置 
		for(j=i+1; j<n; j++) {	//从无序序列中选择一个最小的元素 
			if(r[j]<r[min])	
				min=j;
		}	 
		temp=r[i];	//将最小元素与无序序列的第一个关键字进行交换
		r[i]=r[min];
		r[min]=temp;
	}
}

/*简单选择排序（递减）*/
void SelectSort2(int r[],int n) {
	int i,j,max,temp;
	for(i=0; i<n-1; i++) {	//for循环进行n-1趟 
		max=i;	//max变量记录最小元素的位置 
		for(j=i+1; j<n; j++) {	//从无序序列中选择一个最大的元素
			if(r[j]>r[max])
				max=j;
		}	
		temp=r[i];	//将最大元素与无序序列的第一个关键字进行交换 
		r[i]=r[max];
		r[max]=temp;
	}
}

/*主函数*/
int main() {
	int n;
	int r[MAXSIZE];
	printf("请输入排序表的长度：");
	scanf("%d",&n);
	Create(r,n);
	printf("已建立的序列为：\n");
	Display(r,n);
	SelectSort1(r,n);
	printf("\n");
	printf("递增排序后的序列为：\n");
	Display(r,n);
	SelectSort2(r,n);
	printf("\n");
	printf("递减排序后的序列为：\n");
	Display(r,n);
}

运行结果如下：
在这里插入图片描述
简单选择排序
1、第一趟简单选择排序，从左往右搜索最小的元素，找到-2，将该元素与第一个元素进行交换，由于-2本身处于第一个元素位置，未发生交换；
在这里插入图片描述
2、第二趟简单选择排序，在剩下的无序序列中，从左往右搜索最小的元素，找到0，将该元素与第二个元素进行交换，由于0本身处于第二个元素位置，未发生交换；
在这里插入图片描述
3、第三趟简单选择排序，在剩下的无序序列中，从左往右搜索最小的元素，找到1，将该元素与第三个元素7进行交换；
在这里插入图片描述
4、第四趟简单选择排序，在剩下的无序序列中，从左往右搜索最小的元素，找到3，将该元素与第四个元素7进行交换；
在这里插入图片描述
5、第五趟简单选择排序，在剩下的无序序列中，从左往右搜索最小的元素，找到4，未发生交换；
在这里插入图片描述
此时整个序列已经有序，可以得出，共进行n-1趟排序过程。

（二）算法分析

分析：
（1）空间复杂度：由于额外辅助空间只有一个temp变量，为参数级，所以简单选择排序的空间复杂度为O(1)；
（2）时间复杂度：元素之间的比较次数与初始序列无关，即每次的比较分别是n-1，n-2，……，2，1，即n(n-1)/2=n2/2，所以时间复杂度为O(n2)。
（4）稳定性：简单选择排序是一种不稳定的算法>排序算法。
（5）适用性：简单选择排序可适用于顺序存储和链式存储的线性表。
（6）排序方式：简单选择排序是一种内部排序（In-place）。

二、堆排序

（一）排序思想

1、堆树和大、小根堆

堆排序是利用堆树来进行排序，可以将其视为一棵完全二叉树，树中每一个结点均大于或等于其两个子结点的值，根结点是堆树中的最小值或最大值，即对应小根堆和大根堆。

名称备注
小根堆根结点≥左孩子,右孩子
大根堆根结点≤左孩子,右孩子

基于小根堆得到的序列为递减序列，基于大根堆得到的序列为递增序列。

2、调整根堆

顺序存储的完全二叉树（若结点为i）：
①i的左孩子结点，则为2i；
②i的右孩子结点，则为2i+1；
③i的父结点，则为⌊ i/2 ⌋。

以下以调整大根堆为例，
对于一个大根堆，检查所有非终端结点是否满足大根堆的要求（根结点≤左孩子,右孩子），不满足则进行调整：若当前结点的元素小于左、右孩子中较大者元素，则将当前结点与较大者元素进行交换，使该子树成为堆，若因元素交换破坏了下一级的堆顺序，使不满足堆的性质，则向下继续进行调整。
调整堆的代码如下：

/*堆调整*/
void Adjust(int r[],int low,int high) {
	int i=low,j=2*i;	//r[j]是r[i]的左孩子结点 
	int temp=r[i];
	while(j<=high) {
		if(j<high&&r[j]<r[j+1])	//若当前结点的右孩子较大，则将j指向右孩子 
			j++;
		if(temp<r[j]) {
			r[i]=r[j];	//将r[j]调整至双亲结点的位置上，互换 
			i=j;	//修改i和j的值，以便继续调整 
			j=2*i;
		} else
			break;	//调整结束
	}
	r[i]=temp;		//将被调整的结点放到其应当的位置 
}

1、初始堆树如下：
在这里插入图片描述
2、根据完全二叉树的性质，由下至上进行调整

在顺序存储的完全二叉树中，非叶子结点的编号i≤⌊N/2 ⌋。

由于N=8，可得非叶子结点的编号i≤⌊N/2 ⌋=⌊8/2 ⌋=4，检查所有非终端结点是否满足大根堆的要求，即检查i≤4的结点，且按照从下往上的顺序依次检查。
3、i=4，结点32不满足要求：
在这里插入图片描述
在这里插入图片描述
4、i=3，结点19不满足要求：
在这里插入图片描述
在这里插入图片描述
5、i=2，结点21不满足要求：
在这里插入图片描述
在这里插入图片描述
6、i=1，结点15不满足要求：
在这里插入图片描述
在这里插入图片描述
7、由于经过以上的几轮交换后，可发现结点15不满足大根堆的要求，向下继续进行调整：
在这里插入图片描述
还需调整：
在这里插入图片描述
至此，该完全二叉树符合堆的定义。

3、堆排序

在建立根堆后，将堆中堆顶元素与堆的最后一个元素进行交换，堆顶元素进入有序序列到达最终位置（从无序序列中被排出，符合选择排序的过程），然后对剩下的无序序列继续进行调整，依次进行下去，……，直到无序序列中剩余最后一个元素，此时整个序列已经有序，堆排序结束。
堆排序的代码如下：

/*堆排序*/
void HeapSort(int r[],int n){
	int i,temp;
	for(i=n/2;i>=1;i--)		//建立初始堆 
		Adjust(r,i,n);
	for(i=n;i>1;i--){	//进行n-1次循环，完成堆排序 
		temp=r[1];	//将堆中最后一个元素与堆顶元素交换，将其放入最终位置 
		r[1]=r[i];
		r[i]=temp;
		Adjust(r,1,i-1); 	//对剩下的无序序列进行调整 
	}
}

1、第一趟，将堆顶元素与堆的最后一个元素进行交换，将堆顶元素加入有序子序列，即40与15交换：
在这里插入图片描述
在这里插入图片描述
可看出，此时序列中不满足大根堆的要求（不包括有序子序列40），所以需要恢复大根堆，剩下的无序序列调整为大根堆，调用函数Adjust(r,1,7)：
在这里插入图片描述
在这里插入图片描述
2、第二趟操作也是一样，将堆顶元素与堆的最后一个元素进行交换，将堆顶元素加入有序子序列，即38与19交换：
在这里插入图片描述
剩下的无序序列调整为大根堆，调用函数Adjust(r,1,6)：
在这里插入图片描述
在这里插入图片描述
3、第三趟，33与19交换：
在这里插入图片描述
剩下的无序序列调整为大根堆，调用函数Adjust(r,1,5)：
在这里插入图片描述
在这里插入图片描述
4、第四趟，32与19交换：
在这里插入图片描述
剩下的无序序列调整为大根堆，调用函数Adjust(r,1,4)：
在这里插入图片描述
5、第五趟，29与15交换：
在这里插入图片描述
剩下的无序序列调整为大根堆，调用函数Adjust(r,1,3)：
在这里插入图片描述
6、第六趟，21与19交换：
在这里插入图片描述
剩下的无序序列调整为大根堆，调用函数Adjust(r,1,2)：
在这里插入图片描述
7、第七趟，由于符合大根堆，不用交换：
在这里插入图片描述
剩下最后一个元素，结束，此时得到的序列即为最终结果：
在这里插入图片描述
整体代码如下：

#include<stdio.h>
#define MAXSIZE 100
/*创建函数*/
void Create(int r[],int n) {
	for(int i=0; i<n; i++) {
		printf("输入第%d个元素：",i+1);
		scanf("%d",&r[i]);
	}
}

/*输出函数*/
void Display(int r[],int n) {
	for(int i=0; i<n; i++)
		printf("%d ",r[i]);
}

/*堆调整*/
void Adjust(int r[],int low,int high) {
	int i=low,j=2*i;	//r[j]是r[i]的左孩子结点 
	int temp=r[i];
	while(j<=high) {
		if(j<high&&r[j]<r[j+1])	//若当前结点的右孩子较大，则将j指向右孩子 
			j++;
		if(temp<r[j]) {
			r[i]=r[j];	//将r[j]调整至双亲结点的位置上，互换 
			i=j;	//修改i和j的值，以便继续调整 
			j=2*i;
		} else
			break;	//调整结束
	}
	r[i]=temp;		//将被调整的结点放到其应当的位置 
}

/*堆排序*/
void HeapSort(int r[],int n){
	int i,temp;
	for(i=n/2;i>=1;i--)		//建立初始堆 
		Adjust(r,i,n);
	for(i=n;i>1;i--){	//进行n-1次循环，完成堆排序 
		temp=r[1];	//将堆中最后一个元素与堆顶元素交换，将其放入最终位置 
		r[1]=r[i];
		r[i]=temp;
		Adjust(r,1,i-1); 	//对剩下的无序序列进行调整 
	}
}

/*主函数*/
int main() {
	int n;
	int r[MAXSIZE];
	printf("请输入排序表的长度：");
	scanf("%d",&n);
	Create(r,n);
	printf("已建立的序列为：\n");
	Display(r,n);
	HeapSort(r,n);
	printf("\n");
	printf("排序后的序列为：\n");
	Display(r,n);
}

运行结果如下：
在这里插入图片描述

（二）算法分析

分析：
（1）空间复杂度：堆排序的空间复杂度为O(1)；
（2）时间复杂度：初始建堆的时间复杂度为O(n)，建堆过程中元素对比次数不超过4n，n-1趟交换和建堆过程中，根结点最多下坠h-1层，每下坠一层最多只需对比元素两次，每一趟不超过O(h)=O(log2n)，即堆排序的时间复杂度为O(nlog2n)，故堆排序的时间复杂度均为O(n)+O(nlog2n)=O(nlog2n)。
（3）稳定性：堆排序是一个不稳定的算法>排序算法。
（4）适用性：堆排序只能用于顺序存储结构。
（5）排序方式：堆排序是一种内部排序（In-place）。

三、总结

两种交换排序与前面的插入排序的总结如下表：

算法>排序算法空间复杂度平均时间复杂度最好时间复杂度最坏时间复杂度排序方式稳定性适用性
直接插入排序O(1)O(n2)O(n)O(n2)内部排序（In-place）√顺序存储和链式存储
折半插入排序O(1)O(n2)O(nlog2n)O(n2)内部排序（In-place）√顺序存储
希尔排序O(1)依赖于增量序列依赖于增量序列依赖于增量序列内部排序（In-place）×顺序存储
冒泡排序O(1)O(n2)O(n)O(n2)内部排序（In-place）√顺序存储和链式存储
简单选择排序最好情况为O(log2n)，最坏情况为O(n)O(nlog2n)O(nlog2n)O(n2)内部排序（In-place）×顺序存储
快速排序O(1)O(n2)O(n2)O(n2)内部排序（In-place）×顺序存储和链式存储
堆排序O(1)O(nlog2n)O(nlog2n)O(nlog2n)内部排序（In-place）×顺序存储

http://www.niftyadmin.cn/n/4330.html

相关文章

Linux操作系统和进程基本概念

Linux操作系统和进程基本概念

其实人生在世&#xff0c;是不太需要别人的建议的&#xff0c;不经历过不会明白的。 -Deft 目录 &#x1f3b5;一、冯诺依曼体系和操作系统 &#x1f388;1.1冯诺依曼体系结构 &#x1f388;1.2操作系统 Ⅰ概念 Ⅱ目的 &#x1f3b5;二、进程 &#x1f388;2.1基本概念 …
阅读更多...
理想汽车有增长潜力，但风险也很大

理想汽车有增长潜力，但风险也很大

来源&#xff1a;猛兽财经 作者&#xff1a;猛兽财经 虽然理想汽车的股价去年下跌了逾45%&#xff0c;但猛兽财经认为它未来还有增长潜力&#xff0c;但投资者也需要考虑一些投资理想汽车股票的风险。 总之&#xff0c;以理想汽车目前的股价&#xff0c;理想汽车股票是一项高风…
阅读更多...
OpenCV笔记-对轮廓进行平滑处理

OpenCV笔记-对轮廓进行平滑处理

项目背景 有一个像素数较少的图像&#xff0c;在上面找轮廓&#xff0c;显示轮廓锯齿严重&#xff1b; 如何将轮廓进行平滑&#xff1f; 一开始是想着将轮廓上的拐点拟合出一个贝塞尔曲线&#xff0c;由于要绘制回原图像上&#xff0c;且贝塞尔曲线的生成也没有找到很好的办法&…
阅读更多...
Matlab：控制流

Matlab：控制流

Matlab&#xff1a;控制流条件控制 - if、else、switch条件语句中的数组比较循环控制 - for、while、continue、breakforwhilecontinuebreak程序终止 - return向量化预分配条件控制 - if、else、switch 条件语句可用于在运行时选择要执行的代码块。最简单的条件语句为 if 语句…
阅读更多...
[杂记]算法: 快慢指针

[杂记]算法: 快慢指针

打算以后记录一些比较有代表性的算法. 仅从初学者角度对算法进行简单解读, 以力扣题为例. 0. 快慢指针 快慢指针是双指针的一种. 一般来说, 在判断存不存在环结构的时候比较有用. 通常来讲, 我们通过指针进行遍历, 快指针一次走两步, 慢指针一次走一步, 快慢指针相遇往往就意味…
阅读更多...
Golang手写RPC框架(day1)

Golang手写RPC框架(day1)

Golang手写RPC框架(day1) 我的项目地址 包括项目源码和笔记内容。 Day1 服务端与消息编码 具体流程见 传送门 这里只介绍一下额外的细节和其他知识点。 1.多主程序项目的启动 Goland对于多主程序的项目&#xff0c;可以使用不同的配置来启动不同的项目。 build目录是 使用…
阅读更多...
C语言从0到1之《三子棋》的实现

C语言从0到1之《三子棋》的实现

&#x1f57a;作者启明星使 &#x1f383;专栏&#xff1a;《数据库》《C语言》 &#x1f3c7;分享一句话&#xff1a; 沉香&#xff1a;差一点&#xff0c;怎么总是差一点 杨戬&#xff1a;一定是练功的时候总是差不多&#xff0c;到了关键的时候就是差一点 大家一起加油&…
阅读更多...
java编程思想

java编程思想

文章目录 java编程思想第一章 对象导论面向对象语言OOP的五个特征每个对象都有一个接口每个对象都是提供服务的继承策略设计模式工厂方法设计模式泛型的引入并发，并行，多线程，关于共享资源的线程安全问题客户/服务器技术第二章 一切都是对象用引用操纵对象我们创建的对象存放…
阅读更多...
最新文章

Copyright @ 2022~2023