/**

* 堆排序

* 簡述:

* 首先使用建立最大堆的算法建立好最大堆，然后將堆頂元素(最大值)與最后一個值交換，同時使得堆的長度減小1 ，調(diào)用保持最大堆性質(zhì)的算法調(diào)整，使得堆頂元素成為最大值，此時最后一個元素已被排除在外

* 時間復雜度:

*Θ(nlgn)

* 空間復雜度:

*

* 優(yōu)點:

*

* 缺點:

* 想著就挺麻煩的。。。相比其他排序，相對難理解一點點

* 可改進:

*

* @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;

}

/**

* 保持最大堆的性質(zhì)(孩子不分左右，均比父節(jié)點小)

* @param array，堆中的數(shù)組元素

* @param i，對以該元素為根元素的堆進行調(diào)整，假設(shè)前提:左右子樹都是最大堆

*

* 由于左右孩子都是最大堆，首先比較根元素與左右孩子，找出最大值，假如不是根元素，則調(diào)整兩個元素的值；

* 由于左孩子(右孩子)的值與根元素交換，有可能打破左子樹(右子樹)的最大堆性質(zhì)，因此繼續(xù)調(diào)用，直至葉子元素。

*/

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 );

}

}

/**

* 建立最大堆。在數(shù)據(jù)中，array.length/2+1一直到最后的元素都是葉子元素，因此從其前一個元素開始，一直到第一個元素，重復調(diào)用maxHeapify函數(shù)，使其保持最大堆的性質(zhì)

* @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;

}

}

//調(diào)用保持最大堆性質(zhì)的算法調(diào)整，似的對應(yīng)元素成為最大值，此時最后一個元素已被排除在外

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 );

}

}

}

若有錯誤或不妥之處，敬請諒解并指點。

總結(jié)

以上是生活随笔為你收集整理的java heapsort_排序算法笔记：堆排序 HeapSort in java的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。