排序-堆排序

问题

描述

给指定n个数排序（堆排序）

思路

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

Code

public class heapsort {

    public static void main(String[] args) {
        Scanner as=new Scanner(System.in);
        int n=as.nextInt(),i,z;
        int[] a=new int[n];
        for(i=0;i<n;i++)
            a[i]=as.nextInt();
        for(i=1;i<n;i++) {
            heapinsert(a,i);
        }
        for(i=0;i<n;i++) { System.out.print(a[i]+","); } System.out.println(); for(i=n-1;i>0;i--) {
            z=a[0];
            a[0]=a[i];
            a[i]=z;
            heapimprove(a,i-1);
        }
        for(i=0;i<n;i++) {
            System.out.print(a[i]+",");
        }
    }

    private static void heapimprove(int[] a, int n) {
        int i=0,max,maxi,z;
        if(2*i+2<=n) { if(a[2*i+2]>a[2*i+1]) {
                max=a[2*i+2];
                maxi=2*i+2;
            }else {
                max=a[2*i+1];
                maxi=2*i+1;
            }
        }else {
            if(2*i+1<=n) {
                max=a[2*i+1];
                maxi=2*i+1;
            }else {
                return;
            }
        }
        while(a[i]<max) {
            z=a[i];
            a[i]=max;
            a[maxi]=z;
            i=maxi;
            if(2*i+2<=n) { if(a[2*i+2]>a[2*i+1]) {
                    max=a[2*i+2];
                    maxi=2*i+2;
                }else {
                    max=a[2*i+1];
                    maxi=2*i+1;
                }
            }else {
                return;
            }
        }
    }
    private static void heapinsert(int[] a, int i) {
        int z;
        while(a[(i-1)/2]<a[i]) {
            z=a[(i-1)/2];
            a[(i-1)/2]=a[i];
            a[i]=z;
            i=(i-1)/2;
            if((i-1)/2<0) {
                break;
            }
        }   
    }
}

解析

• 用数组存储堆结构（二叉树），任意节点i（即数组下标为i）的左子节点在数组中的下标为2i+1,右子节点在数组中的下标为2i+2，父节点在数组中的下标为（i-1）/2（注：要注意边界）；
• 先对存储在数组a中的堆做堆的操作使其变成大根堆（大根堆：指在堆中每一棵子数的最大值都是子树的头部结点）；对数组每一个元素遍历调用heapinsert函数构造大根堆；
• 将堆顶元素a[1]与最后一个元素a[n]交换，此时得到新的无序区(a0,a1,……an-2)和新的有序区(Rn-1),且满足a[0,1…n-2]<=R[n-1]；
• 由于交换后新的堆顶a[0]可能违反大根堆的性质，因此需要对当前无序区(a0,a1,……an-2)调整为新大根堆，然后再次将a[0]与无序区最后一个元素交换，得到新的无序区(a0,a1….an-3)和新的有序区(an-2,Rn-1)。不断重复此过程直到有序区的元素个数为n-2，则整个排序过程完成。