文档章节

排序算法(2)--选择排序&堆排序

haoran_10
 haoran_10
发布于 2016/07/15 16:36
字数 1469
阅读 16
收藏 2
点赞 0
评论 0

继续上篇的 交换排序--冒泡排序&快速排序,本篇介绍选择排序和堆排序

 

一、选择排序

非常的简单直观,每次找出最小或者最大的值存储起来,继续找剩下的值存储起来,直达最后一个元素。

  1. 从arr[0]~arr[N]中找出最小的值,放在arr[0],此时arr[0]已经排好序
  2. 从arr[1]~arr[N]中找出最小的值,放在arr[1],
  3. ....从arr[i]~arr[N]中找出最小的值,放在arr[i],
  4. 找到i==N,排序完成

 

public void sort(int[] arr) {
	for(int i=0;i<arr.length;i++){
		
		int min = arr[i];
		int index = i;
		for(int j=i+1;j<arr.length;j++){
			if(min > arr[j]){
				min = arr[j];
				index = j;
			}
		}
		
		int temp = arr[i];
		arr[i] = arr[index];
		arr[index] = temp;
	}
}

 

 

二、堆排序

 堆排序(Heap Sort)是指利用堆这种数据结构所设计的一种排序算法。

堆实际上就是一颗完全二叉树。 堆分为大顶堆和小顶堆,又叫最大堆和最小堆。

大顶堆:父节点比左右节点的值都要大,用来做升序。

小顶堆:父节点比左右节点的值都要小,用来做降序。

 

大顶堆小顶堆是对称关系,理解其中一种即可。本文将对大顶堆实现的升序排序进行详细说明。

堆排序时间复杂度 是O(N*lgN)。

 

 

1、基本思想

(1)、初始化堆:将数列a[0...n]构造成最大堆。
(2)、交换数据:将a[0]和a[n]交换,使a[n]是a[0...n]中的最大值;然后将a[0...n-1]重新调整为最大堆。 接着,将a[1]和a[n-1]交换,使a[n-1]是a[1...n-1]中的最大值;然后将a[1...n-2]重新调整为最大值。 依次类推,直到整个数列都是有序的。

 

2、数组实现的二叉堆的性质数组和堆的对应关系如下:



 

数组和堆有三个对应关系:

(1)、索引为i的左孩子的索引是 (2*i+1);
(2)、索引为i的左孩子的索引是 (2*i+2);
(3)、索引为i的父结点的索引是 floor((i-1)/2);即取整

 

比如30,索引为1,左孩子是40索引是3,右孩子是70索引是4。

 

3、例子演示

(1)、初始化堆

在堆排序算法中,首先要将待排序的数组转化成二叉堆。
下面演示将数组{20,30,90,40,70,110,60,10,100,50,80}转换为最大堆{110,100,90,40,80,20,60,10,30,50,70}的步骤。

 

1.1 i=数组长度/2-1=11/2-1,即i=4



 

 

上面是maxheap_down(a, 4, 10)调整过程。maxheap_down(a, 4, 10)的作用是将a[4...10]进行下调;a[4]的左孩子是a[9],右孩子是a[10]。调整时,选择左右孩子中较大的一个(即a[10])和a[4]交换。

1.2 i=3



 

 

上面是maxheap_down(a, 3, 10)调整过程。maxheap_down(a, 3, 10)的作用是将a[3...10]进行下调;a[3]的左孩子是a[7],右孩子是a[8]。调整时,选择左右孩子中较大的一个(即a[8])和a[4]交换。

1.3 i=2



 


上面是maxheap_down(a, 2, 10)调整过程。maxheap_down(a, 2, 10)的作用是将a[2...10]进行下调;a[2]的左孩子是a[5],右孩子是a[6]。调整时,选择左右孩子中较大的一个(即a[5])和a[2]交换。

1.4 i=1



 


上面是maxheap_down(a, 1, 10)调整过程。maxheap_down(a, 1, 10)的作用是将a[1...10]进行下调;a[1]的左孩子是a[3],右孩子是a[4]。调整时,选择左右孩子中较大的一个(即a[3])和a[1]交换。

交换之后,a[3]为30,它比它的右孩子a[8]要大,接着,再将它们交换。

1.5 i=0



 


上面是maxheap_down(a, 0, 10)调整过程。maxheap_down(a, 0, 10)的作用是将a[0...10]进行下调;a[0]的左孩子是a[1],右孩子是a[2]。调整时,选择左右孩子中较大的一个(即a[2])和a[0]交换。

交换之后,a[2]为20,它比它的左右孩子要大,选择较大的孩子(即左孩子)和a[2]交换。

调整完毕,就得到了最大堆。此时,数组{20,30,90,40,70,110,60,10,100,50,80}也就变成了{110,100,90,40,80,20,60,10,30,50,70}。

(2)、交换数据

在将数组转换成最大堆之后,接着要进行交换数据,从而使数组成为一个真正的有序数组。
交换数据部分相对比较简单,下面仅仅给出将最大值放在数组末尾的示意图。



 

 

上面是当n=10时,交换数据的示意图。
当n=10时,首先交换a[0]和a[10],使得a[10]是a[0...10]之间的最大值;然后,调整a[0...9]使它称为最大堆。交换之后:a[10]是有序的。
当n=9时, 首先交换a[0]和a[9],使得a[9]是a[0...9]之间的最大值;然后,调整a[0...8]使它称为最大堆。交换之后:a[9...10]是有序的。
...
依此类推,直到a[0...10]是有序的。

 

 4、代码

private void maxHeapDown(int arr[],int start,int end){
	int parentIndex = start;//1.1 节点
	int left = 2*parentIndex+1;//1.2 先找到左节点
	
	while(left<=end){
		int maxIndex =left;//2.左右节点中 数据大的节点
		if((left+1) <= end && arr[left]<arr[left+1]){
			maxIndex = left+1;
		}
		
		int parentValue = arr[parentIndex];
		if(parentValue > arr[maxIndex]){
			break;
		}
		
		//3、交换节点
		arr[parentIndex] = arr[maxIndex];
		arr[maxIndex] = parentValue;
		
		//4.继续处理
		parentIndex = maxIndex;
		left = 2*parentIndex+1;
	}
}

public void heapSort(int arr[]){
	 // 从(n/2-1) --> 0逐次遍历。遍历之后,得到的数组实际上是一个(最大)二叉堆。
	for(int i=arr.length/2-1; i>=0; i--){
		maxHeapDown(arr, i, arr.length-1);
	}
	
	for(int i=arr.length-1;i>0;i--){
		int temp = arr[i];
		arr[i] = arr[0];
		arr[0] = temp;//arr[0]和arr[i]交换。交换后arr[i]是arr[0]~arr[i-1]最大的
		
		maxHeapDown(arr, 0, i-1);//对剩余的堆栈进行调整
	}
}

 

 

 

 

 

 

 

© 著作权归作者所有

共有 人打赏支持
haoran_10
粉丝 25
博文 88
码字总数 80846
作品 0
杭州
程序员
排序算法总结(一)---- 直接插入排序,希尔排序(java实现)

一、概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。 二、稳定性,时间复杂度...

ljheee ⋅ 2017/04/08 ⋅ 0

最常用的 8 个排序算法:从原理到改进,再到代码兑现透彻解析

作者:jack 1. 关于排序 很高兴与大家一起探讨计算机科学中的基础算法之排序算法。排序算法是非常基础同时又应用非常广泛的算法,无论在工作还是在生活中,比如: 数据库脚本,如MSSql, MySq...

小数点 ⋅ 2017/12/04 ⋅ 0

8个常用算法的超常剖析

本文来自作者 jack 在 GitChat 上分享「最常用的 8 个排序算法:从原理到改进,再到代码兑现透彻解析」,「阅读原文」查看交流实录 「文末高能」 「更多同类话题」 「查看全部话题」 编辑 | ...

gitchat ⋅ 2017/11/30 ⋅ 0

数据结构之常见的排序算法c语言实现

常见的简单排序算法有冒泡排序、选择排序、插入排序、快排、堆排序、归并排序、希尔排序等,这些排序的理论在网上有很多,这就只给出常见的排序算法源码,上学时候写的,不足之处欢迎大家指正...

菏泽小朱 ⋅ 2016/12/11 ⋅ 0

常见排序算法的稳定性分析和结论

常见排序算法的稳定性分析和结论 这几天笔试了好几次了,连续碰到一个关于常见排序算法稳定性判别的问题,往往还是多选,对于我以及和我一样拿不准的同学可不是一个能轻易下结论的题目,当然...

长平狐 ⋅ 2013/01/06 ⋅ 0

java排序之快速排序、归并排序、基数排序

前两篇说了Java排序中的冒泡、选择、插入、希尔等排序算法,今天就探讨一下剩下的三种常用排序。 快速排序: 当要求时间最快时,就可以用快速排序算法。 选择第一个数为p,小于p的数放在左边...

野小疯 ⋅ 06/05 ⋅ 0

排序算法专项总结

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

jinlong_xu ⋅ 2017/09/10 ⋅ 0

算法系列【希尔排序】篇

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 关于时间复杂度: 1. 平方阶 (O(n2)) 排序各类简单排序:直接插入...

湖南小影 ⋅ 2017/05/18 ⋅ 0

算法系列【希尔排序】篇

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 关于时间复杂度: 1. 平方阶 (O(n2)) 排序各类简单排序:直接插入...

湖南小影 ⋅ 2017/05/18 ⋅ 0

算法系列【希尔排序】篇

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 关于时间复杂度: 1. 平方阶 (O(n2)) 排序各类简单排序:直接插入...

湖南小影 ⋅ 2017/05/18 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

JavaScript零基础入门——(八)JavaScript的数组

JavaScript零基础入门——(八)JavaScript的数组 欢迎大家回到我们的JavaScript零基础入门,上一节课我们讲了有关JavaScript正则表达式的相关知识点,便于大家更好的对字符串进行处理。这一...

JandenMa ⋅ 今天 ⋅ 0

sbt网络问题解决方案

转自:http://dblab.xmu.edu.cn/blog/maven-network-problem/ cd ~/.sbt/launchers/0.13.9unzip -q ./sbt-launch.jar 修改 vi sbt/sbt.boot.properties 增加一个oschina库地址: [reposit......

狐狸老侠 ⋅ 今天 ⋅ 0

大数据,必须掌握的10项顶级安全技术

我们看到越来越多的数据泄漏事故、勒索软件和其他类型的网络攻击,这使得安全成为一个热门话题。 去年,企业IT面临的威胁仍然处于非常高的水平,每天都会看到媒体报道大量数据泄漏事故和攻击...

p柯西 ⋅ 今天 ⋅ 0

Linux下安装配置Hadoop2.7.6

前提 安装jdk 下载 wget http://mirrors.hust.edu.cn/apache/hadoop/common/hadoop-2.7.6/hadoop-2.7.6.tar.gz 解压 配置 vim /etc/profile # 配置java环境变量 export JAVA_HOME=/opt/jdk1......

晨猫 ⋅ 今天 ⋅ 0

crontab工具介绍

crontab crontab 是一个用于设置周期性被执行的任务工具。 周期性执行的任务列表称为Cron Table crontab(选项)(参数) -e:编辑该用户的计时器设置; -l:列出该用户的计时器设置; -r:删除该...

Linux学习笔记 ⋅ 今天 ⋅ 0

深入Java多线程——Java内存模型深入(2)

5. final域的内存语义 5.1 final域的重排序规则 1.对于final域,编译器和处理器要遵守两个重排序规则: (1)在构造函数内对一个final域的写入,与随后把这个被构造对象的引用赋值给一个引用...

江左煤郎 ⋅ 今天 ⋅ 0

面试-正向代理和反向代理

面试-正向代理和反向代理 Nginx 是一个高性能的反向代理服务器,但同时也支持正向代理方式的配置。

秋日芒草 ⋅ 今天 ⋅ 0

Spring 依赖注入(DI)

1、Setter方法注入: 通过设置方法注入依赖。这种方法既简单又常用。 类中定义set()方法: public class HelloWorldOutput{ HelloWorld helloWorld; public void setHelloWorld...

霍淇滨 ⋅ 昨天 ⋅ 0

马氏距离与欧氏距离

马氏距离 马氏距离也可以定义为两个服从同一分布并且其协方差矩阵为Σ的随机变量之间的差异程度。 如果协方差矩阵为单位矩阵,那么马氏距离就简化为欧氏距离,如果协方差矩阵为对角阵,则其也...

漫步当下 ⋅ 昨天 ⋅ 0

聊聊spring cloud的RequestRateLimiterGatewayFilter

序 本文主要研究一下spring cloud的RequestRateLimiterGatewayFilter GatewayAutoConfiguration @Configuration@ConditionalOnProperty(name = "spring.cloud.gateway.enabled", matchIfMi......

go4it ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部