选择排序

选择排序基本思想是:每一次在n-i+1i=1,2,3,••••,n-1)个记录中选取键值最小的记录作为有序序列的第i个记录。基本分类有直接选择排序和堆排序两种方式。下面分别介绍

直接选择:


思想:在第i次选择操作中,通过n-i次键值比较,从n-i+1个记录中选出键值最小的记录,并和第i个记录交换

算法描述为:
Void SelectSort(List R,int n)
{
Int min, i ,j;
For(i=1;i<=n=1;i++)//每次循环选出一个最小值
{
Min=i; //假设第i个键值最小
For(j=i+1;j<=n;j++)
 
If(R[j].key<R[min].key) min=j;   //记录下键值较小的记录下
If(min!=i) swap(R[min],R[i]);    //将最小值记录和第i个记录交换
} 
}


从代码中可以开出,代码的辅助变量为3个整型变量,与问题的规模无关,所以空间复杂度为O(1),而时间复杂度是双重的n次循环,所以时间复杂度为O(n*n

实例初始关键字 [49 38 65 97 76 13 27 49]进行直接排序。排序过程和结果如下

第一趟排序后 13 [38 65 97 76 49 27 49]

第二趟排序后 13 27 [65 97 76 49 38 49]

第三趟排序后 13 27 38 [97 76 49 65 49]

第四趟排序后 13 27 38 49 [76 97 65 49 ]

第五趟排序后 13 27 38 49 49 [97 65 76]

第六趟排序后 13 27 38 49 49 65 [97 76]

第七趟排序后 13 27 38 49 49 65 76 [97]

最后排序结果 13 27 38 49 49 65 76 97

堆排序


堆排序是对直接排序的优化,是在n-1次比较所得的信息,减少以后各次选择中的比较次数。基于以上分析。推导出堆排序

学习堆排序前,先讲解下什么是数据结构中的二叉堆。


二叉堆的定义


二叉堆是完全二叉树或者是近似完全二叉树。

二叉堆满足二个特性:

1.父结点的键值总是大于或等于(小于或等于)任何一个子节点的键值。

2.每个结点的左子树和右子树都是一个二叉堆(都是最大堆或最小堆)。

当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。下图展示一个最小堆:



由于其它几种堆(二项式堆,斐波纳契堆等)用的较少,一般将二叉堆就简称为堆。

堆的存储


一般都用数组来表示堆,i结点的父结点下标就为(i – 1) / 2。它的左右子结点下标分别为2* i + 1和2 * i + 2。如第0个结点左右子结点下标分别为1和2。



如何创建一个堆?


首先将要排序的所有键值看成是一颗完全二叉树的各个结点(这个时候并不一定具备对特性),根据完全二叉树性质,最后一个非终端结果是第|n/2|个元素,对于i>|n/2|的结点k(i)都没有孩子结点,这样以K(i)为根的子树是堆。所以只需从|n/2|开始,逐步把 k[n/2],k[(n/2)-1], k[(n/2)-2], k(i)为根的子树筛选为堆就完成了建立堆的过程.

实例,对集合{ 40 ,10,30 ,50}对应的二叉树,筛选堆的过程如下


n=4, n/2=2,所以从k(2)开始执行,10<50,不调整,K(1) 40>10,进行调整



基本的建立过程就是上图的表示了。

时间复杂度为O(N * logN),共N -1次重新恢复堆操作。

直接选择排序和堆排序是很类似的,每次都是将最小的数据并入到后面的有序区间,故操作完成后整个数组就有序了。

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

智能推荐

FFMPEG完美入门资料---002---FFmpeg 支持能力说明

接着上文写: 2.3.1 FFmpeg 对编码解码器的支持 ffmpeg 支持的编解码器种类共有 280 多种, 涵盖了几乎所有常见音视频编码格式, 能解码几乎所有的音视频, 每种音视频编解码器的实现都在 libavcodec 目录下有具体的 C 语言实现。 * 注:编码器和解码器的名称不是完全匹配的,因此有些编码器没有对应相同名称的解码器,反之, 解码器也一样。即使编码和解码都支持也不一定是完全...

20145107 《Java程序设计》第五次实验报告

实验简述: 在本周,我们进行了Java的第五次试验,本次实验的主要内容是结对编程。本次实验的大体过程是: 1.先进行Java的客户端与服务端的代码编写。结对是两个人,一人负责客户端,一人负责服务端。 2.利用加解密代码包,编译运行代码,客户端加密,服务器解密。 3.客户端加密明文后将密文通过TCP发送。 4.在本次的代码编写上,要求代码可以实现两者之间的数据传输,在代码传输的基础上加上一定的加密过...

更改springboot启动拼成的字母

1.更改springboot启动拼成的字母 其实很好改,只需要在resources下新建一个txt文件就可以,命名为banner.txt,那这种字符该怎么拼出来呢,下面推荐一个网址,有这种工具 传送门 2.集成...

Node.js安装配置

好久都没更新博客了,今天心血来潮,决定是时候更新一篇了,首先我们来认识一下node.js。 什么是node.js? 简单的说 Node.js 就是运行在服务端的 JavaScript。 Node.js 是一个基于Chrome JavaScript 运行时建立的一个平台。 Node.js是一个事件驱动I/O服务端JavaScript环境,基于Google的V8引擎,V8引擎执行Javascript的...

RocketMQ之双Master集群搭建笔记记录

一:RocketMQ双master集群部署 服务器环境(我采用的虚拟机,centos6 .5【特别注意:安装的虚拟机centos系统一定得是64位的,32位的会启动不起来。即便起来了也会有很多问题,深坑勿踩】)  ip       用户名    密码        角色     模式 192.168.197.101   root        nameServer1,brokerServer1  ...

猜你喜欢

蓝桥杯试题集-基础练习题-数列特征(Java)

//做题笔记,仅自己看得懂 题目: 正确姿势:...

多线程爬取4k超高清美图壁纸

多线程爬取4k美图壁纸 前言:看完此篇文章你可以更加深入的了解多线程的使用,并且最重要的你能够下载你自己想要的超高清4k壁纸 爬取结果: 1. 分析网站 要爬取的url :http://pic.netbian.com/ a) 判断网页是动态加载还是静态加载页面。右击查看网页源代码,按Ctrl + f在源代码中搜索网站的详情页地址,从而判断整个网页是静态加载的 b) 明确爬取的目标。我们要爬取的目标...

elementUI-添加自定义图标

elementui的小图标有限,跟UI给的不一样,这个时候咋办呢?百度走起。。。。参考了两篇博主分享的 自定义elementui中的图标 和 建立图标库,这里主要用到第一种 实际中: elementUI导航栏 具体代码: 汉字转换Unicode编码: 直接打开控制台: 汉字.chatCodeAt().toString(16); 然后回车; 至于三角形的图标,我直接把箭头的 unicode 值改成了...

[Linux]——文件缓冲区

文件缓冲区 提到文件缓冲区这个概念我们好像并不陌生,但是我们对于这个概念好像又是模糊的存在脑海中,之间我们在介绍c语言文件操作已经简单的提过这个概念,今天我们不妨深入理解什么是文件缓冲区。 为什么需要文件缓冲区 当我们在程序中写下一条printf语句时,我们希望将这条语句的内容打印到屏幕上。但是如果你将语句放在循环中,难道你执行一次循环那么操作系统就要打印一次这条数据么?答案当然不是 我们对于程序...

基于FPGA的IIC协议详解——EEPROM控制器(1)

IIC协议举例 常用IIC协议使用地方 常见IIC协议的注意点 24LC64芯片读写命令的时序图 eeprom控制器的系统框图 时序图设计 代码设计 EEPROM控制器测试模块的代码 结束语 常用IIC协议使用地方 熟悉一个协议一定要知道这个协议应该用到什么地方,IIC协议作为飞利浦公司定义的一个慢速传输协议,常用于: 1、芯片寄存器的配置; 2、eeprom的读写; 本次实验我们将使用eepro...