算法学习——堆排序

堆排序就是将要排序的对象构造为一个有序的大顶堆或小顶堆（根据需要来定，升序排序构造大顶堆，降序排序构造小顶堆），之后每次将堆顶选出后剩下的节点元素再次进行排序，直到剩下最后一个节点元素为止，此时排序结束。

 

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--)//构造一个小顶堆

                            adjustMinSort(array,i,len-1);

                   for(i=len-1;i>=0;i--)//循环一次将最小的数挑出来，剩下的数再进行堆排序

                   {

                            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]+" ");

                   }

         }

}