堆排序算法介绍
堆是一种重要的数据结构,为一棵完全二叉树, 底层如果用数组存储数据的话,假设某个元素为序号为i(Java数组从0开始,i为0到n-1),如果它有左子树,那么左子树的位置是2i+1,如果有右子树,右子树的位置是2i+2,如果有父节点,父节点的位置是(n-1)/2取整。分为最大堆和最小堆,最大堆的任意子树根节点不小于任意子结点,最小堆的根节点不大于任意子结点。所谓堆排序就是利用堆这种数据结构来对数组排序,我们使用的是最大堆。处理的思想和冒泡排序,选择排序非常的类似,一层层封顶,只是最大元素的选取使用了最大堆。最大堆的最大元素一定在第0位置,构建好堆之后,交换0位置元素与顶即可。堆排序为原位排序(空间小),
且最坏运行时间是O(n2),是渐进最优的比较排序算法。
堆排序算法Java实现
如《插入排序(Insertsort)之Java实现》一样,先实现一个数组工具类。代码如下:
- publicclassArrayUtils{
- publicstaticvoidprintArray(int[]array){
- System.out.print("{");
- for(inti=0;i<array.length;i++){
- System.out.print(array[i]);
- if(i<array.length-1){
- System.out.print(",");
- }
- }
- System.out.println("}");
- }
- publicstaticvoidexchangeElements(int[]array,intindex1,intindex2){
- inttemp=array[index1];
- array[index1]=array[index2];
- array[index2]=temp;
- }
- }
堆排序的大概步骤如下:
- 构建最大堆。
- 选择顶,并与第0位置元素交换
- 由于步骤2的的交换可能破环了最大堆的性质,第0不再是最大元素,需要调用maxHeap调整堆(沉降法),如果需要重复步骤2
堆排序中最重要的算法就是maxHeap,该函数假设一个元素的两个子节点都满足最大堆的性质(左右子树都是最大堆),只有跟元素可能违反最大堆性质,那么把该元素以及左右子节点的最大元素找出来,如果该元素已经最大,那么整棵树都是最大堆,程序退出,否则交换跟元素与最大元素的位置,继续调用maxHeap原最大元素所在的子树。该算法是分治法的典型应用。具体代码如下:
- publicclassHeapSort{
- publicstaticvoidmain(String[]args){
- int[]array={9,8,7,6,5,4,3,2,1,0,-1,-2,-3};
- System.out.println("Beforeheap:");
- ArrayUtils.printArray(array);
- heapSort(array);
- System.out.println("Afterheapsort:");
- ArrayUtils.printArray(array);
- }
- publicstaticvoidheapSort(int[]array){
- if(array==null||array.length<=1){
- return;
- }
- buildMaxHeap(array);
- for(inti=array.length-1;i>=1;i--){
- ArrayUtils.exchangeElements(array,0,i);
- maxHeap(array,i,0);
- }
- }
- privatestaticvoidbuildMaxHeap(int[]array){
- if(array==null||array.length<=1){
- return;
- }
- inthalf=array.length/2;
- for(inti=half;i>=0;i--){
- maxHeap(array,array.length,i);
- }
- }
- privatestaticvoidmaxHeap(int[]array,intheapSize,intindex){
- intleft=index*2+1;
- intright=index*2+2;
- intlargest=index;
- if(left<heapSize&&array[left]>array[index]){
- largest=left;
- }
- if(right<heapSize&&array[right]>array[largest]){
- largest=right;
- }
- if(index!=largest){
- ArrayUtils.exchangeElements(array,index,largest);
- maxHeap(array,heapSize,largest);
- }
- }
- }
堆排序算法介绍
堆是一种重要的数据结构,为一棵完全二叉树, 底层如果用数组存储数据的话,假设某个元素为序号为i(Java数组从0开始,i为0到n-1),如果它有左子树,那么左子树的位置是2i+1,如果有右子树,右子树的位置是2i+2,如果有父节点,父节点的位置是(n-1)/2取整。分为最大堆和最小堆,最大堆的任意子树根节点不小于任意子结点,最小堆的根节点不大于任意子结点。所谓堆排序就是利用堆这种数据结构来对数组排序,我们使用的是最大堆。处理的思想和冒泡排序,选择排序非常的类似,一层层封顶,只是最大元素的选取使用了最大堆。最大堆的最大元素一定在第0位置,构建好堆之后,交换0位置元素与顶即可。堆排序为原位排序(空间小),
且最坏运行时间是O(n2),是渐进最优的比较排序算法。
堆排序算法Java实现
如《插入排序(Insertsort)之Java实现》一样,先实现一个数组工具类。代码如下:
- publicclassArrayUtils{
- publicstaticvoidprintArray(int[]array){
- System.out.print("{");
- for(inti=0;i<array.length;i++){
- System.out.print(array[i]);
- if(i<array.length-1){
- System.out.print(",");
- }
- }
- System.out.println("}");
- }
- publicstaticvoidexchangeElements(int[]array,intindex1,intindex2){
- inttemp=array[index1];
- array[index1]=array[index2];
- array[index2]=temp;
- }
- }
堆排序的大概步骤如下:
- 构建最大堆。
- 选择顶,并与第0位置元素交换
- 由于步骤2的的交换可能破环了最大堆的性质,第0不再是最大元素,需要调用maxHeap调整堆(沉降法),如果需要重复步骤2
堆排序中最重要的算法就是maxHeap,该函数假设一个元素的两个子节点都满足最大堆的性质(左右子树都是最大堆),只有跟元素可能违反最大堆性质,那么把该元素以及左右子节点的最大元素找出来,如果该元素已经最大,那么整棵树都是最大堆,程序退出,否则交换跟元素与最大元素的位置,继续调用maxHeap原最大元素所在的子树。该算法是分治法的典型应用。具体代码如下:
- publicclassHeapSort{
- publicstaticvoidmain(String[]args){
- int[]array={9,8,7,6,5,4,3,2,1,0,-1,-2,-3};
- System.out.println("Beforeheap:");
- ArrayUtils.printArray(array);
- heapSort(array);
- System.out.println("Afterheapsort:");
- ArrayUtils.printArray(array);
- }
- publicstaticvoidheapSort(int[]array){
- if(array==null||array.length<=1){
- return;
- }
- buildMaxHeap(array);
- for(inti=array.length-1;i>=1;i--){
- ArrayUtils.exchangeElements(array,0,i);
- maxHeap(array,i,0);
- }
- }
- privatestaticvoidbuildMaxHeap(int[]array){
- if(array==null||array.length<=1){
- return;
- }
- inthalf=array.length/2;
- for(inti=half;i>=0;i--){
- maxHeap(array,array.length,i);
- }
- }
- privatestaticvoidmaxHeap(int[]array,intheapSize,intindex){
- intleft=index*2+1;
- intright=index*2+2;
- intlargest=index;
- if(left<heapSize&&array[left]>array[index]){
- largest=left;
- }
- if(right<heapSize&&array[right]>array[largest]){
- largest=right;
- }
- if(index!=largest){
- ArrayUtils.exchangeElements(array,index,largest);
- maxHeap(array,heapSize,largest);
- }
- }
- }
分享到:
相关推荐
java的堆排序算法实现程序,含测试,可直接运行。java的堆排序算法实现程序,含测试,可直接运行。
主要介绍了Java实现堆排序(Heapsort)实例代码,有需要的朋友可以参考一下
主要介绍了java 数据结构之堆排序(HeapSort)详解及实例的相关资料,需要的朋友可以参考下
heapSort 方法实现了堆排序算法。它使用以下步骤进行排序: 构建最大堆:从非叶子节点开始向上调整,使得父节点的值大于等于子节点的值。 排序阶段:依次从堆顶(最大值)开始,将堆顶元素与末尾元素交换,然后...
Java 写得最大堆排序代码,给大家参考下,自己刚写的。
用java实现的常用排序,都可以编译运行。 包括shellSort, quickSort, mergeSort, heapSort
堆排序Java中的堆排序实现
java写的八大经典排序算法(win7 jdk 1.6 下运行) ...堆排序 HeapSort 插入排序 InsSort 快速排序 QuickSort 归并排序 MergeSort 基数排序 BucketSort 简单选择排序 SelectSort 希尔排序 ShellSort
将待排序序列构造成一个大顶堆 此时,整个序列的最大值就是堆顶的根节点。 将其与末尾元素进行交换,此时末尾就为最大值。 然后将剩余n-1个元素重新构造成一个堆,这样会得到n个元素的次小值。如此反复执行...
ED2-堆排序 堆排序算法的实现
堆排序 执行 3 向堆排序
:thinking_face: 算法 ...堆排序-HeapSort :lion:搜索算法-搜索 与搜索相关的数据结构:二叉查找树,平衡查找树,散列表 线性查找-LinearSearch 二分查找-BinarySearch 广度优先搜索 深度优先搜索
常用排序算法总结,包括插入排序(InsertionSort),冒泡排序(BubbleSort),选择排序(SelectionSort),快速排序(QuickSort... * 二路归并排序(MergeSort),堆排序(HeapSort)。有每一种排序算法的复杂度分析以及实现思路~
目录 02.字符串 03.树 04.哈希表 05.栈和队列 06.图 07.位运算 08.链表 程序基本输入输出 基础算法 返回目录 # English Title ...Java ...Java ...Java ...Java ...Java ...Java ...Java ...Java ...Java ...Java ...HeapSort 堆排序 Java 1
汉诺塔java源码 ForPower 一些个人的学习笔记的归档,相关目录内容如下: Arithmetic Atoi.java,实现 atoi,将字符串转为整数 BackPack.java,背包算法。 BasicSort.java,基数排序。...堆排序。 InsertionS
数据结构与算法 对于Hacktoberfest 2018... 以上几点示例:Java中的堆排序应进入java/heapsort.java 您可以选择仅包含算法的功能或整个程序。 如果您所用语言的文件夹不存在,请创建一个新文件夹。 不要害怕进行公关
leetcode切割分组 java_algorithm this is a sorting algorithm demo. created by ...堆排序 QuickSort 快速排序 平均时间复杂度 O(n + k) 空间复杂度 O(k) CountingSort | 计数排序 | 用一个计算器
堆排序及有关方法。 2,BitTree.Java ;二叉树的遍历 3,DataSort.Java;排序算法 4,堆排的第二种思路 LeetCode322 :给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的...
主题包括联合查找,二进制搜索,堆栈,队列,包,插入排序,选择排序,shellsort,quicksort,3向quicksort,mergesort,heapsort,binary堆,binary搜索树,red-black树,分离链和线性探测哈希表,Graham扫描和kd...