选择排序

标签: 选择排序  简单选择排序  堆排序

本次介绍选择排序,选择排序共有两个排序方法:

1、简单选择排序——不稳定的排序方法
2、推排序——不稳定的排序方法

首先,还是简单了解一下选择排序的思想:每次从待排序的记录中选出最小的记录,然后把它放在已经有序序列的最前面

然后,同其他排序方法相同,数据存储的结构为:

typedef struct{
	int key;
}ElemType;
typedef struct{
	ElemType r[MAXSIZE+1];
	int length;
}SqList;

简单选择排序一共需要进行n-1趟,每趟比较n-i次,比较出最小的记录,如果不是H.r[i],则进行交换。

简单选择排序的算法如下:

void SimpleSelectSort(SqList &H)
{
	int i,j,k;
	for(i=1;i<H.length;i++)
	{
		k=i;
		for(j=i+1;j<=H.length;j++)
		{		
			if(H.r[j].key<H.r[k].key)
				k=j;
		} 
		if(k!=i)
		{
			H.r[0]=H.r[i];
			H.r[i]=H.r[k];
			H.r[k]=H.r[0];
		} 
	}
}

简单选择排序的时间复杂度和空间复杂度为:

T(n)=O(n^2)
S(n)=O(1)

接下来介绍堆排序,堆排序分为小顶堆和大顶堆。

小顶堆选择排序后 -> 非递增序列
大顶堆选择排序后 -> 非递减序列

如果想要运用堆排序,现需要进行初建堆操作。如果把记录看成一个完全二叉树的话,我们应该先寻找第一个非叶子结点,然后从第一个非叶子结点到最后一个结点进行堆排序。第一个非叶子结点为:H.length/2。

初建堆完成以后,进行排序操作,把第一个记录和最后一个记录进行交换,然后把第一个结点和他的左右孩子(假设第一个结点为s,左孩子就为2s,右孩子为2s+1)的关键字大小进行比较,把其中较大的记录放到堆顶,然后依次类推,直到确定最小的记录的位置。

下面为推排序的算法:

void HeapAdjust(SqList &H,int s,int m)
{
	ElemType rc;
	rc=H.r[s];
	int j;
	for(j=2*s;j<=m;j*=2)
	{
		if(j<m&&H.r[j].key<H.r[j+1].key)
			j++;
		if(rc.key>H.r[j].key)
			break;
		H.r[s]=H.r[j];
		s=j;
	} 
	H.r[s]=rc;
} 

void Heap(SqList &H)
{
	int i;
	for(i=H.length/2;i>0;i--)//从第一个非叶子结点开始 
		HeapAdjust(H,i,H.length);//先把顺序表排序成为大顶堆
	for(i=H.length;i>1;i--)
	{
		H.r[0]=H.r[1];
		H.r[1]=H.r[i];
		H.r[i]=H.r[0];
		HeapAdjust(H,1,i-1);
	} 
}

堆排序的时间复杂度和空间复杂度:

T(n)=O(nlog2n)
S(n)=O(1)

选择排序完整的程序如下:

#include<stdio.h>
#include<iostream>
using namespace std;

#define MAXSIZE 20

typedef struct{
	int key;
}ElemType;
typedef struct{
	ElemType r[MAXSIZE+1];
	int length;
}SqList;
SqList H;

void SimpleSelectSort(SqList &H)
{
	int i,j,k;
	for(i=1;i<H.length;i++)
	{
		k=i;
		for(j=i+1;j<=H.length;j++)
		{		
			if(H.r[j].key<H.r[k].key)
				k=j;
		} 
		if(k!=i)
		{
			H.r[0]=H.r[i];
			H.r[i]=H.r[k];
			H.r[k]=H.r[0];
		} 
	}
}

void HeapAdjust(SqList &H,int s,int m)
{
	ElemType rc;
	rc=H.r[s];
	int j;
	for(j=2*s;j<=m;j*=2)
	{
		if(j<m&&H.r[j].key<H.r[j+1].key)
			j++;
		if(rc.key>H.r[j].key)
			break;
		H.r[s]=H.r[j];
		s=j;
	} 
	H.r[s]=rc;
} 

void Heap(SqList &H)
{
	int i;
	for(i=H.length/2;i>0;i--)//从第一个非叶子结点开始 
		HeapAdjust(H,i,H.length);//先把顺序表排序成为大顶堆
	for(i=H.length;i>1;i--)
	{
		H.r[0]=H.r[1];
		H.r[1]=H.r[i];
		H.r[i]=H.r[0];
		HeapAdjust(H,1,i-1);
	} 
}

int main()
{
	int i,output,input=1;
	while(input)
	{
		cout<<"*********************************************************************"<<endl;
		cout<<"请输入想要执行命令的序号:"<<endl;
		cout<<"0:退出程序"<<endl;
		cout<<"1:执行简单选择排序操作"<<endl;
		cout<<"2:执行堆排序操作"<<endl;
		cout<<"*********************************************************************"<<endl;
		cin>>output;
		switch(output)
		{
			case 0:
				input=0;
				break;
			case 1:
				cout<<"执行简单选择排序操作"<<endl;
				cout<<"请输入顺序表表长:"<<endl;
				cin>>H.length;
				cout<<"请依次输入顺序表的元素:"<<endl;
				for(i=1;i<=H.length;i++)
					cin>>H.r[i].key;
				SimpleSelectSort(H);
				cout<<"执行简单选择排序操作后的结果为:"<<endl;
				for(i=1;i<=H.length;i++)
					cout<<H.r[i].key<<" ";
				cout<<endl;
				break;
			case 2:
		 		cout<<"执行堆排序操作"<<endl;
				cout<<"请输入顺序表表长:"<<endl;
				cin>>H.length;
				cout<<"请依次输入顺序表的元素:"<<endl;
				for(i=1;i<=H.length;i++)
					cin>>H.r[i].key;
				Heap(H);
				cout<<"执行堆排序操作后的结果为:"<<endl;
				for(i=1;i<=H.length;i++)
					cout<<H.r[i].key<<" ";
				cout<<endl;
				break;
		}
	}
}

EG: 49 38 65 97 76 13 27 49
运行结果如下图所示:
在这里插入图片描述

版权声明:本文为qq_42717239原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_42717239/article/details/91298432

智能推荐

使用Xdebug进行远程调试

为什么要用? 方便联调: 和客户端一起联调,是die(); exit(); 会影响其他人员是使用。 关注数据变化: 正常情况下,我们在调试和开发时,更关注数据的变化。频繁断点、效率比较低。 简单: 之前的开发自己比较懒,一直没用,用起来发现很简单。 原理 运行xdebug需要客户端IDE(phpstorm)、远程服务器配合,首先是客户端配置好端口,发送debug请求,请求会通过浏览器或者IDE的h...

【教程向】通过windows在树莓派3B上安装Ubuntu MATE 16.04.2 (Xenial)

本文参考了http://www.ituring.com.cn/article/273613 ================================================================= 1:因为树莓派3B的性能问题,所以使用这个特别为树莓派设计的版本。 2:准备: 树莓派3B * 1 16GB TF/Micro SD卡 *1(尽量用速度快一些的卡,因为以后这相...

LeetCode(7 整数反转)

如题 这就不用分析了,直接依次取每位即可,难点就是个越界判断...

Caused by: java.rmi.ConnectIOException: error during JRMP connection establishment; nested exception

启动RMI报如下错误: 最后发现是端口冲突造成的,当时用的5003端口启动服务端的RMI刚好和本地的一个服务端口冲突。 输入netstat -aon|findstr "5003"查询它的pid为3056 继续输入tasklist|findstr "3056",查看是哪个进程或者程序占用了5003端口,结果是:magentproc.exe 找到PID后可以直接...

猜你喜欢

【LeetCode(Java) - 322】零钱兑换

文章目录 1、题目描述 2、解题思路 3、解题代码 1、题目描述 2、解题思路   定义 dp[i] 表示对于组成金额 i 的最少硬币个数。   如果方案存在,那么至少有一个硬币至少出现了一次:   如果是第 0 个硬币出现了一次,则:dp[i] = dp[i-coins[0]] + 1   如果是第 1 个硬币出现了...

在Visual Studio 2013中配置Entity Framework使用MySQL

环境 使用的软件及版本 - Microsoft Visual Studio Ultimate 2013 (版本 12.0.40629.00 Update 5) - Microsoft.Net Framework 版本 4.6.01055 - MySQL版本: 5.6.17 步骤 1. 创建空的MVC项目 2. 安装扩展 3. 在数据库中建立对应的表 必须在数据库内先新建表,否则asp.net mv...

Python才是世界上最好的言语,php,java靠边站

伟大的入门编程语言有什么特征呢?或者换一种方式问,“当我们教他们编程时,应该给予他们什么?”对于成年人和青少年学生,我认为以下五点非常重要。 学生从入门语言获得的五样东西 非常棒的首次体验,就像一本书的第一页,首先需要“入迷”,学习新知识不可避免的会遇到挫折,但要有持续的热情和好奇心,这对于那些从未接触过编码的年轻人来说是至关重要的; Web编程的能...

动态调整docker容器cpu资源

目的:动态调整系统cpu核数后,如何在不停止容器服务的情况下,docker动态使用最新的CPU资源 事件由来:     1、在ucloud上购买了一台可以热升级的机器,热升级指的是动态更改系统cpu和内存资源     2、随着业务的扩展,发现cpu、内存负载过高,需要在不停止业务的情况下动态扩容,因此使用了ucloud提供的热升级服务,从4核12G扩容为8核...

用python itchat包 爬取微信好友头像形成矩形头像集

原创作品,转载请注明作者 abysscarry-袁杰丶 初学python,我们必须干点有意思的事!从微信下手吧! 头像集样例如下: 大家可以发朋友圈开启辨认大赛哈哈~ 话不多说,直接上代码,注释我写了比较多,大家应该能看懂 运行结果: ok!!!...