Java排序算法总结之堆排序
本篇章节讲解Java排序算法总结之堆排序。分享给大家供大家参考。具体分析如下: 1991年计算机先驱奖获得者、斯坦福大学计算机科学系教授罗伯特?弗洛伊德(Robert W.Floyd)和威廉姆斯(J.Williams)在1964年共同发明了著名的堆排序算法( Heap Sort )。本文主要介绍堆排序用Java来实现。 堆积排序(Heapsort)是指利用堆积树(堆)这种资料结构所设计的一种排序算法,可以利用数组的特点快速定位指定索引的元素。堆排序是不稳定的排序方法,辅助空间为O(1), 最坏时间复杂度为O(nlog2n) ,堆排序的堆序的平均性能较接近于最坏性能。 堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征,使得在当前无序区中选取最大(或最小)关键字的记录变得简单。 (1)用大根堆排序的基本思想 ① 先将初始文件R[1..n]建成一个大根堆,此堆为初始的无序区 代码实现: public class Test { public static int[] Heap = { 10,32,1,9,5,7,12,4,3 }; // 预设数据数组 public static void main(String args[]) { int i; // 循环计数变量 int Index = Heap.length; // 数据索引变量 System.out.print("排序前: "); for (i = 1; i < Index - 1; i++) System.out.printf("%3s",Heap); System.out.println(""); HeapSort(Index - 2); // 堆排序 System.out.print("排序后: "); for (i = 1; i < Index - 1; i++) System.out.printf("%3s",Heap); System.out.println(""); } /** * 建立堆 */ public static void CreateHeap(int Root,int Index){ int i,j; // 循环计数变量 int Temp; // 暂存变量 int Finish; // 判断堆是否建立完成 j = 2 * Root; // 子节点的Index Temp = Heap[Root]; // 暂存Heap的Root 值 Finish = 0; // 预设堆建立尚未完成 while (j <= Index && Finish == 0) { if (j < Index) // 找最大的子节点 if (Heap[j] < Heap[j + 1]) j++; if (Temp >= Heap[j]) Finish = 1; // 堆建立完成 else { Heap[j / 2] = Heap[j]; // 父节点 = 目前节点 j = 2 * j; } } Heap[j / 2] = Temp; // 父节点 = Root值 } public static void HeapSort(int Index) { int i,j,Temp; // 将二叉树转成Heap for (i = (Index / 2); i >= 1; i--) CreateHeap(i,Index); // 开始进行堆排序 for (i = Index - 1; i >= 1; i--) { Temp = Heap; // Heap的Root值和最后一个值交换 Heap = Heap[1]; Heap[1] = Temp; CreateHeap(1,i); // 对其余数值重建堆 System.out.print("排序中: "); for (j = 1; j <= Index; j++) System.out.printf("%3s",Heap[j]); System.out.println(""); } } } 堆可以被看成是一棵树,结点在堆中的高度可以被定义为从本结点到叶子结点的最长简单下降路径上边的数目;定义堆的高度为树根的高度。我们将看到,堆结构上的一些基本操作的运行时间至多是与树的高度成正比,为O(lgn)。通过阅读本文,希望能帮助到你。 希望本文所述对大家的java程序设计有所帮助。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |