堆排序

堆排序（Heap Sort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

算法描述

将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

动图演示

05.gif

实例

代码实现

public class HeapTest {
    public static void main(String[] args) {
        int[] sort ={3,2,1,4,6,5,8,9,10,7} ;
        System.out.println("排序前：");
        printArray(sort);
        heapSort(sort);
        System.out.println("\n排序后：");
        printArray(sort);
    }
    
    public static void printArray(int[] array) {
        System.out.print("{");
        int len=array.length;
        for (int i = 0; i < len; i++) {
            System.out.print(array[i]);
            if (i < len - 1) {
                System.out.print(", ");
            }
        }
        System.out.println("}");
    }
    
    public static void heapSort(int[] a){
       int len = a.length;
       for (int i = 0;i < len ;i++) {
           sink(a,len-1-i);
           exch(a,0,len-1-i);
           
       } 
       

    }
    
    /**
    * 创建堆算法
    */
    public static void sink(int[] a,int lastIndex) {
        for(int i = (lastIndex-1)/2;i >= 0;i--) {
            int k = i;
            while(2 * k + 1 <= lastIndex) {
                int bigIndex = 2*k+1;
                if(bigIndex < lastIndex) {
                    if(a[bigIndex] < a[bigIndex + 1]) {
                        bigIndex++;
                    }
                }
                
                if(a[k] < a[bigIndex]) {
                    exch(a,k,bigIndex);
                    k = bigIndex;
                }else {
                    break;
                }
            }
        }
    }
    
    /**
    * 交换两元素
    */
    public static void exch(int[] a,int i,int j) {
        if(i == j) {
            return;
        }
        a[i] = a[i] + a[j];
        a[j] = a[i] - a[j];
        a[i] = a[i] - a[j];
        
    }
}