/** * <ul> * <li>平均情况:O(nlog(2)n)</li> * <li>最好情况:O(nlog(2)n)</li> * <li>最坏情况:O(nlog(2)n)</li> * <li>辅助存储:O(1)</li> * <li>不稳定</li> * <ul> * * @timestamp Mar 12, 2016 6:56:54 PM * @author smallbug */ public class HeapSort { public static void main(String[] args) { int[] data = DataUtil.getData(50); System.out.println(Arrays.toString(data)); long time = System.currentTimeMillis(); heapSort(data); System.out.println(Arrays.toString(data)); System.out.println("speed " + (System.currentTimeMillis() - time) + " ms"); System.out.println("排序是否成功:" + (DataUtil.verify(data, DataUtil.ASC) ? "是" : "否")); } private static void heapSort(int[] data) { createHeap(data); heapSortDetail(data); } private static void heapSortDetail(int[] data) { // 末尾与头交换,交换后调整最大堆 for (int i = data.length - 1; i > 0; i--) { int temp = data[0]; data[0] = data[i]; data[i] = temp; maxHeapify(data, i, index2Cood(0)); } } private static void createHeap(int[] data) { int startIndex = getParentIndex(data.length); for (int i = startIndex; i >= 0; i--) { maxHeapify(data, data.length, index2Cood(i)); } } private static void maxHeapify(int[] data, int heapSize, int cood) { // 当前点与左右子节点比较 int leftIndex = getChildLeftIndex(cood); int rightIndex = getChildRightIndex(cood); int largest = cood; if (leftIndex < heapSize && data[cood2Index(cood)] < data[leftIndex]) { largest = index2Cood(leftIndex); } if (rightIndex < heapSize && data[cood2Index(largest)] < data[rightIndex]) { largest = index2Cood(rightIndex); } // 得到最大值后可能需要交换,如果交换了,其子节点可能就不是最大堆了,需要重新调整 if (largest != cood) { int temp = data[cood2Index(cood)]; data[cood2Index(cood)] = data[cood2Index(largest)]; data[cood2Index(largest)] = temp; maxHeapify(data, heapSize, largest); } } /** * 索引转坐标 * * @timestamp 2016年8月23日 上午11:12:01 * @param index * @return */ private static int index2Cood(int index) { return index + 1; } /** * 坐标转索引 * * @timestamp 2016年8月23日 上午11:11:51 * @param cood * @return */ private static int cood2Index(int cood) { return cood - 1; } /** * 根据子元素坐标获取父元素索引 * * @timestamp 2016年8月23日 上午11:30:27 * @param cood * @return */ private static int getParentIndex(int cood) { return cood2Index(cood >>> 1); } /** * 左子节点position注意括号,加法优先级更高 * * @param current * @return */ private static int getChildLeftIndex(int cool) { return cood2Index(cool << 1); } /** * 右子节点position * * @param current * @return */ private static int getChildRightIndex(int cool) { return cood2Index(cool << 1) + 1; } }
相关推荐
堆排序是一种基于比较的排序算法,它通过构造一个大顶堆或小顶堆来实现排序。在本场景中,我们关注的是堆排序的源代码,它适用于openSUSE 11.4操作系统,并且是使用GCC version 4.5.1编译器编译的。在这个名为"sort...
本主题将深入探讨四种常见的排序算法:堆排序、快速排序以及两种未在标题中明确提到但同样重要的排序方法——基数排序和计数排序。 首先,让我们详细了解一下堆排序。堆排序是一种基于比较的排序算法,利用了数据...
堆排序是一种基于比较的排序算法,它通过构造一个大顶堆或小顶堆来实现排序。在大顶堆中,父节点的值总是大于或等于其子节点;而在小顶堆中,父节点的值总是小于或等于其子节点。在C++中,我们可以利用STL中的`...
【堆排序算法详解】 堆排序是一种高效的比较排序算法,其主要思想是利用堆这种数据结构进行数据的排序。堆是一个近似完全二叉树的结构,同时满足堆的性质:即父节点的键值总是大于或等于(在最大堆中)或小于或等于...
堆排序是一种基于比较的排序算法,它利用了数据结构中的“堆”这一概念。在计算机科学中,堆通常被理解为一个完全二叉树,其中每个父节点的值都大于或等于(大顶堆)或小于或等于(小顶堆)其子节点的值。堆排序算法...
在这个名为“学生成绩管理中实现堆排序”的项目中,我们看到一个C++编写的学生成绩管理系统,它使用了堆排序方法来管理并排序学生的成绩。 首先,让我们详细了解一下堆。堆通常是一个完全二叉树,可以分为最大堆和...