堆排序就是將要排序的對(duì)象構(gòu)造為一個(gè)有序的大頂堆或小頂堆（根據(jù)需要來定，升序排序構(gòu)造大頂堆，降序排序構(gòu)造小頂堆），之后每次將堆頂選出后剩下的節(jié)點(diǎn)元素再次進(jìn)行排序，直到剩下最后一個(gè)節(jié)點(diǎn)元素為止，此時(shí)排序結(jié)束。

?

package pp.suanfa;

?

/**

?* 堆排序

?* @author xiaoGd

?*

?*/

?

public class HeapSort {

????????

???????? public static void adjustMinSort(int[] array,int pos,int len)

???????? {

?????????????????? int temp;

?????????????????? int child;

?????????????????? for(temp=array[pos];2*pos+1<=len;pos=child)

?????????????????? {

??????????????????????????? child = 2*pos + 1;

??????????????????????????? if(child<len&&array[child]>array[child+1])

???????????????????????????????????? child++;

??????????????????????????? if(temp>array[child])

???????????????????????????????????? array[pos] = array[child];

??????????????????????????? else

???????????????????????????????????? break;

?????????????????? }

?????????????????? array[pos] = temp;

???????? }

????????

???????? public static void myMinHeapSort(int[] array)

???????? {

?????????????????? int i;

?????????????????? int len = array.length;

?????????????????? for(i=len/2-1;i>=0;i--)//構(gòu)造一個(gè)小頂堆

??????????????????????????? adjustMinSort(array,i,len-1);

?????????????????? for(i=len-1;i>=0;i--)//循環(huán)一次將最小的數(shù)挑出來，剩下的數(shù)再進(jìn)行堆排序

?????????????????? {

??????????????????????????? int temp = array[0];

??????????????????????????? array[0] = array[i];

??????????????????????????? array[i] = temp;

??????????????????????????? adjustMinSort(array,0,i-1);

?????????????????? }

???????? }

???????? public static void main(String[] args) {

?????????????????? int[] array = {5,7,2,4,6,9,8,1,0,3};

?????????????????? myMinHeapSort(array);

?????????????????? for(int i=0;i<array.length;i++)

?????????????????? {

??????????????????????????? System.out.print(array[i]+" ");

?????????????????? }

???????? }

}