文档章节

排序---->选择排序

小强斋太
 小强斋太
发布于 2016/11/09 20:07
字数 2936
阅读 1
收藏 0
点赞 0
评论 0

选择排序

选择排序的基本思想是:每一趟从n-i+1 (i=1,2,…,n)个元素中选取一个关键字最小的元素作为有序序列中第i个元素。在简单选择排序的基础上,对其进行改进的算法有树型选择排序堆排序

 

4.1简单选择排序

基本思想

简单选择排序的基本思想非常简单,即:第一趟,从n个元素中找出关键字最小的元素与第一个元素交换;第二趟,在从第二个元素开始的n-1个元素中再选出关键字最小的元素与第二个元素交换;如此,第k趟,则从第k个元素开始的n-k+1个元素中选出关键字最小的元素与第k 个元素交换,直到整个序列按关键字有序。选择排序是不稳定的排序方法。 

例子:

代码实现

代码实现1

//选择排序
	public void selectSort(Object[] r, int low, int high){
		for (int k=low; k<high-1; k++){
			int min = k;
			for (int i=min+1; i<=high; i++)
				if (strategy.compare(r[i],r[min])<0) min = i;
			if (k!=min){
				Object temp = r[k];
				r[k] = r[min];
				r[min] = temp;
			}
		}
	}

代码实现2

import junit.framework.TestCase;

public class CollectSort extends TestCase {
	// 选择排序
	public void sort(Integer a[]) {
		int min;
		int temp;
		for (int i = 0; i < a.length - 1; i++) {
			min = i; // 本次排序最小的

			for (int j = i + 1; j < a.length; j++) {
				if (a[j] < a[min]) {
					min = j;
				}

			}
			if (min != i) {
				temp = a[min];
				a[min] = a[i];
				a[i] = temp;
			}

		}

	}

	public void test() {
		Integer array[] = { 49, 38, 65, 97, 76, 13, 27, 49 };
		sort(array);

		for (int i = 0; i < array.length; i++) {
			System.out.print(array[i] + "  ");

		}

	}

}
效率分析

空间效率:显然简单选择排序只需要一个辅助空间。

时间效率:在简单选择排序中,所需移动元素的次数较少,在待排序序列已经有序的情况下,简单选择排序不需要移动元素,在最坏的情况下,即待排序序列本身是逆序时,则移动元素的次数为3(n-1)。然而无论简单选择排序过程中移动元素的次数是多少,任何情况下,简单选择排序都需要进行n(n-1)/2次比较操作,因此简单选择排序的时间复杂度为O(n2)。

算法改进思想:从上述效率分析中可以看出,简单选择排序的主要操作是元素间的比较操作,因此改进简单选择排序应从减少元素比较次数出发。在简单选择排序中,首先从n个元素的序列中选择关键字最小的元素需要n-1次比较,在n-1个元素中选择关键字最小的元素需要n-2次比较……,在此过程中每次选择关键字最小的元素都没有利用以前比较操作得到的结果。欲降低比较操作的次数,则需要把以前比较的结果记录下来,由此得到一种改进的选择类排序算法,即树型选择排序。

 

4.2树型选择排序-----锦标赛排序

基本思想

树型选择排序也称为锦标赛排序。其基本思想是:先把待排序的n个元素两两进行比较,取出较小者,若轮空则直接进入下一轮比较;然后在⎡n/2⎤个较小者中,采用同样的方法进行比较,再选出较小者;如此反复,直到选出关键字最小的元素为止。重复上述过程,直到所有元素全部输出为止,则得到按关键字有序的序列。

举例:

这个过程可以使用一颗具有n个结点的完全二叉树来表示,最终选出的关键字最小的元素就是这棵二叉树的根结点。例如图(a)给出了对8 个元素的关键字{ 26, 53 , 48 , 11 , 13 , 48 , 32 , 15}选出最小关键字元素的过程。

在输出关键字最小的元素后,为选出次小关键字,可以将最小关键字元素所对应的叶子结点的关键字设置为∞,然后从该叶子结点起逆行向上,将所经过的结点与其兄弟进行比较,修改从该叶子结点到根结点上各结点的值,则根结点的值即为次小关键字。

例如,在图(a)的基础上输出最小关键字11 后,输出次小关键字13 的过程如图(b)所示。

在图(b)的基础上输出最小关键字13 后,输出次小关键字15 的过程如图(c)所示。

重复上述过程,直到所有元素全部输出为止,则得到按关键字有序的序列。

代码实现
效率分析

时间效率:在树型选择排序过程中为找到关键字最小的元素一共进行了n-1次比较,此后每次找出一个关键字所需要的比较次数等于完全二叉树的高度h,而具有n 个叶子结点的完全二叉树其高度为⎡log n⎤,由此可知除最小关键字外,每选择一个次小关键字需要进行⎡log n⎤次比较,因此树型选择排序的时间复杂度T(n)=(n-1)⎡logn⎤+(n-1)= Ο(nlog n)。

空间效率:与简单选择排序相比,虽然树型选择排序减小的时间复杂度,却使用了更多的辅助空间,在树型选择排序中共使用了n-1 个而外的存储空间存放以前的比较结果。

算法改进思想:树型选择排序的缺点是使用了较多的辅助空间,以及和∞进行多余比较,为弥补树型选择排序的这些缺点,J.W.J.Williams 在1964年提出了进一步的改进方法,即堆排序。

 

4.3堆排序

堆的定义

堆的定义为:n个元素的序列{k1 , k2 , … , kn},当且仅当满足下列关系时,称之为堆。

(1)ki<=k2iki<=k2i+1(1≤i≤ n),或者(2)ki>=k2iki>=k2i+1(1≤i≤ n),

若满足条件①,则称为小顶堆,若满足条件②,则称为大顶堆。

 如果将序列{k1 , k2 , … , kn}对应为一维数组,且序列中元素的下标与数组中下标一致,即数组中下标为0 的位置不存放数据元素,此时该序列可看成是一颗完全二叉树,则堆的定义说明,在对应的完全二叉树中非终端结点的值均不大于(或不小于)其左右孩子结点的值。由此,若堆是大顶堆,则堆顶元素——完全二叉树的根——必为序列中n个元素的最大值;反之,若是小顶堆,则堆顶元素必为序列中n个元素的最小值。

(a)是一个大顶堆,(b)是一个小顶堆。其对应的元素序列分别为{45 , 26 , 18 , 23, 19 , 5 , 11 , 14}、{13 , 32 , 15 , 40, 51 , 38}。

基本思想

设有n 个元素,欲将其按关键字排序。可以首先将这n个元素按关键字建成堆,将堆顶元素输出,得到n个元素中关键字最大(或最小)的元素。然后,再将剩下的n-1个元素重新建成堆,再输出堆顶元素,得到n个元素中关键字次大(或次小)的元素。如此反复执行,直到最后只剩一个元素,则可以得到一个有序序列,这个排序过程称之为堆排序。

实现堆排序时需要解决两个问题

1. 输出堆顶元素后,怎样调整剩余n-1 个元素,使其按关键字成为一个新堆?

设有一个具有m个元素的堆,输出堆顶元素后,剩下m-1个元素。具体的调整方法是:

首先,将堆底元素(最后一个元素)送入堆顶,此时堆被破坏,其原因仅是根结点不满足堆的性质,而根结点的左右子树仍是堆。然后,将根结点与左、右子女中较大(或较小)的进行交换。若与左孩子交换,则左子树堆被破坏,且仅左子树的根结点不满足堆的性质;若与右孩子交换,则右子树堆被破坏,且仅右子树的根结点不满足堆的性质。继续对不满足堆性质的子树进行上述交换操作,直到叶子结点,则堆被重建。我们称这个自根结点到叶子结点的调整过程为筛选。

例子

图(a)为一个大顶堆,在输出堆顶元素53之后,将堆底元素26送入堆顶,如图(b)所示;然后将26与36、42中大的元素交换,交换后,以26为根的子树已是一个堆;此时筛选结束,得到一个新堆,如图(c)所示。如果继续输出堆顶元素42,然后重建堆,则结果如图(d)所示。

2 如何由n个元素的初始序列构造一个堆?

实际上建堆的方法是逐层向上对每个非终端结点进行一次筛选即可。

例子:

对于待排序的初始序列{28 , 26 , 17 , 36, 20 , 42 , 11 , 53},初始建堆的过程如图所示。(a)是由初始序列得到的完全二叉树;初始建堆首的过程,以按层从下到上的第一个非叶子结点开始,即从36开始,对36进行调整,过程如图(b)所示,调整结果如图(c)所示;然后对下一个非叶子结点17进行调整,调整过程如图(c),结果如图(d)所示;继续上述过程直到根结点28 为止,对28 进行调整后,即得到一个大顶堆,结果如图(f)所示。

代码实现
//堆排序
	public void heapSort(Object[] r){
		int n = r.length - 1;
		for (int i=n/2; i>=1; i--)
			heapAdjust(r,i,n);
		for (int i=n; i>1; i--){
			Object temp = r[1];
			r[1] = r[i];
			r[i] = temp;
			heapAdjust(r,1,i-1);
		}
	}
	//调整r[low..high]使之成为大顶堆
	////已知r[low..high]中除r[low]之外,其余元素均满足堆的定义
	private void heapAdjust(Object[] r, int low, int high){
		Object temp = r[low];
		for (int j=2*low; j<=high; j=j*2){
			if (j<high&&strategy.compare(r[j],r[j+1])<0) j++;
			if (strategy.compare(temp,r[j])>=0) break;
			r[low] = r[j];	low = j;
		}
		r[low] = temp;
	}
效率分析

空间效率:显然堆排序只需要一个辅助空间。

时间效率:首先,对于深度为k的堆,heapAdjust算法中所需执行的比较次数至多为2k次。则在初始建堆的过程中,对于具有n个元素、深度为h的堆而言,由于在i层上最多有2^i个结点,以这些结点为根的二叉树深度最大为h-i,那么⎣n/2⎦次调用heapAdjust时总共进行的关键字比较次数Tinit为:

即,初始化需要执行的比较操作的次数为Ο(n)。

其次,在排序过程中,每输出一次堆顶元素需要进行一次调整,而每次调整所需的比较次数为Ο(log n),因此n次输出总共需要的比较次数为Ο(nlogn)。由此,堆排序在任何情况下,其时间复杂度为Ο(nlogn)。这相对于快速排序而言是堆排序的最大优点。

堆排序在元素较少时由于消耗较多时间在初始建堆上,因此不值得提倡,然而当元素较多时还是很有效的排序算法。

© 著作权归作者所有

共有 人打赏支持
小强斋太
粉丝 0
博文 181
码字总数 0
作品 0
广州
排序算法篇_选择排序法

image   选择排序(Selection Sort)也是比较简单的排序算法,思路也比较直观。选择排序算法在每一步中选取最小值来重新排列,从而达到排序的目的。 选择排序算法 选择排序算法通过选择和交...

一笑小先生 ⋅ 01/30 ⋅ 0

排序——简单选择排序

一、选择排序概念 选择排序(Selection Sort)的基本思想:对n个记录进行扫描,选择最小的记录,将其输出,接着在剩下的n-1个记录中扫描,选择最小的记录将其输出……不断重复这个过程,直到...

翼动动空 ⋅ 2016/06/06 ⋅ 0

直接选择排序(Straight Selection Sort)

1、定义 选择排序(Selection Sort)的基本思想是:每一趟从待排序的记录中选出关键字最小的记录,顺序放在已排好序的子文件的最后,直到全部记录排序完毕。 常用的选择排序方法有直接选择排序...

野渡书生 ⋅ 2016/05/03 ⋅ 0

数据结构与算法(冒泡排序与选择排序)

1.冒泡排序 冒泡排序是一种简单的排序算法,它重复的遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换,遍历数列的工作是重复的进行直到没有需要交换的元素。 冒泡排序算...

墨痕hz ⋅ 06/06 ⋅ 0

史上最简单!冒泡、选择排序的Python实现及算法优化详解

1、排序概念 内部排序和外部排序 根据排序过程中,待排序的数据是否全部被放在内存中,分为两大类: 内部排序:指的是待排序的数据存放在计算机内存中进行的排序过程; 外部排序:指的是排序...

马哥教育 ⋅ 2017/10/25 ⋅ 0

选择排序—简单选择排序

简单选择排序是一种选择排序。 选择排序:每趟从待排序的记录中选出关键字最小的记录,顺序放在已排序的记录序列末尾,直到全部排序结束为止。 简单排序处理流程: (1)从待排序序列中,找到关...

DCX_abc ⋅ 2017/11/15 ⋅ 0

Java常用算法解析及示例(一)

1.冒泡排序 冒泡算法的主要逻辑是,假设有N个数,游标从第一位数开始,若左边的数比右边的数大,则左边交换,游标移向下一位直到最后一位。 在游标移动过程中,可以保证,右边的数一定比左边...

魔都太阳神 ⋅ 06/15 ⋅ 0

菜鸟教程选择排序算法c++版

选择排序算法详细分析 选择排序的定义:假如我们是把待排序的数组中的数据从小到大进行排序,下面我们先需要知道2个额外知识就是我们一个选择排序算法拿到一个数组和一个数组的元素个数之后,...

qq_33060405 ⋅ 2017/12/13 ⋅ 0

经典排序算法python回顾之二 选择排序

选择排序: 简介 首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素...

vincent_y ⋅ 2013/12/19 ⋅ 0

排序算法专项总结

1、选择排序,是每一次从未排序序列中找出一个最大或者最小的数,放到已排好序的数列最后。因此关键字比较次数跟数列的初始排列顺序是没有关系的。 2、初始数据集排列顺序与比较次数无关的有...

jinlong_xu ⋅ 2017/09/10 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

ARMS: 原来实时计算可以这么简单!

摘要: 业务实时监控服务( ARMS)是一款阿里云应用性能管理(APM)类监控产品。借助本产品,您可以基于前端、应用、业务自定义等服务,迅速便捷地为企业构建秒级响应的业务监控能力。 业务实...

阿里云云栖社区 ⋅ 3分钟前 ⋅ 0

Monkey入门_琉璃

先下载android sdk安装配置好路径,然后adb shell 如果给你显示这个,说明目前没有有效的移动设备链接,可以开个安卓模拟器或者使用真机,usb或wifi链接到电脑都可以,打开usb调试模式;然后...

EvanDev ⋅ 4分钟前 ⋅ 0

Idea类注释模板

一、设置类注释模板 1.选择File–>Settings–>Editor–>File and Code Templates–>Includes–>File Header. 2.设置完成后,创建类时自动生成注释,效果如下。...

Clarence_D ⋅ 6分钟前 ⋅ 0

vuejs题

1、active-class是哪个组件的属性?嵌套路由怎么定义? 答:vue-router模块的router-link组件。 2、怎么定义vue-router的动态路由?怎么获取传过来的动态参数? 答:在router目录下的index.j...

自由小鸟 ⋅ 6分钟前 ⋅ 0

2018年社交系统ThinkSNS年中大促

致各大商企事业单位及粉丝用户: 为感谢大家对ThinkSNS品牌的关注与支持,2018年6月18日官方诚推出:年中大促,限时抢购活动! “ThinkSNS 年中大促,¥6.18超值特惠 名额有限,预购从速! ...

ThinkSNS账号 ⋅ 11分钟前 ⋅ 0

MYSQL主从复制搭建及切换操作(GTID与传统)

如下: MYSQL主从复制方式有默认的复制方式异步复制,5.5版本之后半同步复制,5.6版本之后新增GTID复制,包括5.7版本的多源复制。 MYSQL版本:5.7.20 操作系统版本:linux 6.7 64bit 1、异步...

rootliu ⋅ 12分钟前 ⋅ 0

Java强软弱虚引用Reference

Java强软弱虚引用Reference 本文目的:深入理解Reference 本文定位:学习笔记 学习过程记录,加深理解,提升文字组合表达能力。也希望能给学习Reference的同学一些灵感 源码说明 源码基于jdk...

lichuangnk ⋅ 14分钟前 ⋅ 0

plsql 表中字段及注释时为乱码

在windows中创 建一个名为“NLS_LANG”的系统环境变量,设置其值为“SIMPLIFIED CHINESE_CHINA.ZHS16GBK”, 然后重新启动 pl/sql developer,这样检索出来的中文内容就不会是乱码了。如...

江戸川 ⋅ 17分钟前 ⋅ 0

Docker创建JIRA 7.2.7中文破解版

1、介绍 1.1、什么是JIRA?   关于JIRA网上的介绍有很多,以下摘自百度百科:   JIRA是Atlassian公司出品的项目与事务跟踪工具,被广泛应用于缺陷跟踪、客户服务、需求收集、流程审批、任...

谢思华 ⋅ 21分钟前 ⋅ 0

Java Class 类使用

Java Class 类使用 我们可以通过已知的包名来获取到 Class 对象,从而可以通过反射动态的来操作对象。 获取Class有三种方式 //通过对象.class直接获取Class integerClass = Integer.class;...

gaob2001 ⋅ 26分钟前 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部