南阳做玉器网站,seo百度关键词优化软件,软文营销实施背景,鄂州网站制作哪家好/*** 堆排序* 简述:* 首先使用建立最大堆的算法建立好最大堆#xff0c;然后将堆顶元素(最大值)与最后一个值交换#xff0c;同时使得堆的长度减小1 #xff0c;调用保持最大堆性质的算法调整#xff0c;使得堆顶元素成为最大值#xff0c;此时最后一个元素已被排除在外* …/*** 堆排序* 简述:* 首先使用建立最大堆的算法建立好最大堆然后将堆顶元素(最大值)与最后一个值交换同时使得堆的长度减小1 调用保持最大堆性质的算法调整使得堆顶元素成为最大值此时最后一个元素已被排除在外* 时间复杂度:*Θ(nlgn)* 空间复杂度:** 优点:** 缺点:* 想着就挺麻烦的。。。相比其他排序相对难理解一点点* 可改进:** author CheN**/public class HeapSort {private static int heapSize;//左孩子编号private static int getLeftChild(int i){return 2 * i;}//右孩子编号private static int getRightChild(int i){return 2 * i 1;}/*** 保持最大堆的性质(孩子不分左右均比父节点小)* param array堆中的数组元素* param i对以该元素为根元素的堆进行调整假设前提:左右子树都是最大堆** 由于左右孩子都是最大堆首先比较根元素与左右孩子找出最大值假如不是根元素则调整两个元素的值* 由于左孩子(右孩子)的值与根元素交换有可能打破左子树(右子树)的最大堆性质因此继续调用直至叶子元素。*/private static void maxHeapify( int[] array , int index ){int left getLeftChild( index );int right getRightChild( index );int largest 0;if( left heapSize array[ index ] array[ left ]){largest left;}else{largest index;}if( right heapSize array[ right ] array[ largest ]){largest right;}if( largest index ){return ;} else {int temp array[ index ];array[ index ] array[ largest ];array[ largest ] temp;maxHeapify( array, largest );}}/*** 建立最大堆。在数据中array.length/21一直到最后的元素都是叶子元素因此从其前一个元素开始一直到第一个元素重复调用maxHeapify函数使其保持最大堆的性质* param array*/private static void buildMaxHeap(int[] array){for( int i array.length / 2 ; i 1; i-- ){maxHeapify( array , i );}}/*** 堆排序:*/public static void asc( int[] array ){// 找出最小元素,并将其置于array[0]int min array[0];for(int i 1 ; i array.length ; i ){if( min array[i] ){min array[i];array[i] array[0];array[0] min;}}//调用保持最大堆性质的算法调整似的对应元素成为最大值此时最后一个元素已被排除在外heapSize array.length;buildMaxHeap( array );for(int i array.length - 1 ; i 2 ; i--){int temp array[1];array[1] array[i];array[i] temp;heapSize--;maxHeapify( array , 1 );}}}若有错误或不妥之处敬请谅解并指点。
