Java排序算法 堆排序

1991年计算机先驱奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德(RobertW．Floyd)和威廉姆斯(J．Williams)在1964年共同发明了著名的堆排序算法( Heap Sort)。本文主要介绍堆排序用Java来实现。

AD：

public class HeapSort  { 
    publicstatic void main(String[] args)  
    { 
       int[] a = {26, 5, 77, 1, 61, 11, 59, 15, 48, 19}; 
         
       Sort(a);  
    } 
   ////小堆排序
    publicstatic void Sort(int[] a)  
    { 
       int n = a.length;  
       int temp = 0;  
         
       Display(a, "Before sort : ");  
         
       for(int i=n/2; i>0; i--)  
           Adjust(a, i-1, n);  
         

       for(int i=n-2; i>=0; i--)  
       {  
           temp = a[i+1];  
           a[i+1] = a[0];  
           a[0] = temp;  
             
           Adjust(a, 0, i+1);  
       }  
         
       Display(a, "After  sort : "); 
    } 
     
   public  static void Adjust(int[] a, int i, int n) 
    { 
       int j = 0;  
       int temp = 0;  
         
       temp = a[i];     
       j = 2 * i + 1;  
         
       while(j <= n-1)  
       {  
           if(j < n-1 && a[j]< a[j+1])  
               j++;  
             
           if(temp >= a[j])  
               break;  
             
           a[(j-1)/2] = a[j];  
             
           j = 2 * j + 1;
           Display(a, "----- ");  
       }  
         
       a[(j-1)/2] = temp;  
    } 
     
    publicstatic void Display(int[] a, String str)  
    { 
       System.out.println(str);  
         
       for(int i=0; i<a.length; i++) 
           System.out.print(a[i] + " ");  
         
       System.out.println();  
   }