- 从arr[0]~arr[N]中找出最小的值,放在arr[0],此时arr[0]已经排好序
- 从arr[1]~arr[N]中找出最小的值,放在arr[1],
- ....从arr[i]~arr[N]中找出最小的值,放在arr[i],
- 找到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)是指利用堆这种数据结构所设计的一种排序算法。
(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)、索引为i的左孩子的索引是 (2*i+2);
(3)、索引为i的父结点的索引是 floor((i-1)/2);即取整
在堆排序算法中,首先要将待排序的数组转化成二叉堆。
下面演示将数组{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]是有序的。
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);//对剩余的堆栈进行调整 } }
相关推荐
常用的排序算法--堆排序,通过创建堆的方法进行排序
排序算法:排序算法汇总--各类排序算法 冒泡,选择,插入,快排,归并,堆排
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
最快的排序算法 谁才是最强的排序算法:快速排序-归并排序-堆排序,排序算法数据结构
各类排序算法整理--C语言描述--本人编写 排序算法种类有: 冒泡 快速排序 堆排序 希尔排序 插入排序 选择排序 二路归并排序
堆排序的源程序--编译、运行成功的。 其基本算法思想参照《算法导论》。 有点编译器需去掉-system("pause");
最优堆排序算法最优堆排序算法最优堆排序算法最优堆排序算法最优堆排序算法最优堆排序算法
经典排序算法 - 堆排序Heap sort序 经典排序算法 - 地精排序Gnome Sort 经典排序算法 - 奇偶排序Odd-even sort 经典排序算法 - 梳排序Comb sort 经典排序算法 - 耐心排序Patience Sorting 经典排序算法 - 珠...
Java代码-排序-直接插入排序、希尔排序、直接选择排序、冒泡排序、堆排序、快速排序、归并排序中部分排序以及算法-贪心法,大家可以将源码下载下来进行学习,附带着注释和解释,有不理解的可以找博主一起探讨,共同...
此文件为数据结构中的九种排序算法,包含一些排序方法的过程,其九种排序包括:直接插入排序,折半插入排序,希尔排序,冒泡排序,快速排序,选择排序,堆排序,归并排序,基数排序!
详解Java常用排序算法-堆排序
七大排序算法如下: 交换排序:快速排序quicksort,冒泡排序bubblesort...选择排序:直接选择排序selectionsort,堆排序maxheapsort 插入排序:直接插入排序insertsort,希尔排序shellsort 合并排序:归并排序mergesort
简单的堆排序算法:以定长数组为例,动态数组等可以以此类推
内容简介: 涵盖 - 插入排序 & - 冒泡排序 & - 选择排序 & - 希尔排序 & - 归并排序 & - 快速排序 & - 计数排序 & - 堆排序 模板与解析。 适合人群: 普及早期的萌新 OIer 们。
7大排序算法(快速排序,冒泡排序,选择排序,归并排序,插入排序,希尔排序,堆排序)实现源码
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
自己看书时写的排序算法:堆排序 CPP文件
一个堆排序算法 c++写的 逻辑相同 可自行 改为java 写一个堆排序算法 c++ 写一个堆排序算法 c++ 写一个堆排序算法 c++ 写一个堆排序算法 c++ 写一个堆排序算法 c++ 写一个堆排序算法 c++ 写一个堆排序算法 c++ 写一...
排序作为最基础的算法,有选择排序,冒泡排序,插入排序,希尔排序,堆排序,快速排序,归并排续等,我会用c++写一下,欢迎交流~
C++实现常用排序算法 (快速,归并,选择,谢尔,堆排序)