堆排序

堆排序是直接选择排序的一种改进算法，先将数组调整成一个堆，在将堆第一个元素最小元素和待排序区间最后一个元素交换。重新调整堆,重复执行n - 1次即可得到有序数组

具体解释代码注释中有说明，注意完全二叉树的性质如i节点的左子树节点为2 * i是从1开始，不是从0开始。实现的时候需要注意一下

1.创建一个大根堆或者小根堆

2.交换第一个和最后一个，调整1 ~ n - 1为大根堆

3.交换第一个和倒数第二个，调整1 ~ n - 2为大根堆

...

主要是建堆和调整堆，其中，建堆也是调用调整实现的

HeapSort.java

 1 package com.gxf.heapsort;
 2 
 3 /**
 4  * 堆排序
 5  * 堆排序是对直接选择排序的一种改进算法
 6  * 将待排序列rec[]调整成堆，即rec[i]<=rec[2 * i] && rec[i]<=rec[2 * i + 1]
 7  * 如果将整个序列看成是遍历一棵完全二叉树得到的，这棵树的性质可以总结为根节点小于左右节点的值
 8  * 
 9  * 主要两步
10  * 1.建堆，将带排序调整为一个堆
11  * 2.取根节点即最小元素rec[0]，将剩下的调整为一个堆，重复执行n - 1
12  * @author Administrator
13  *
14  */
15 public class HeapSort {
16     Rec rec = new Rec();
17     /**
18      * 一次调整
19      * 调整元素rec[k]满足堆的性质，end为rec最后位置， k + 1到 end满足堆的性质
20      * 1.暂存rec[k],选出k的左右子节点2k 2k + 1中较小的min和rec[k]进行比较，如果rec[k]<min结束调整，else to 2.
21      * 2.将min的值放到rec[k]中
22      * 3.查看调整过后的子树是否满足堆的性质
23      * @param rec
24      * @param k
25      * @param end
26      */
27     public void shift(Rec rec[], int k, int end){
28         Rec temp = new Rec();//暂存rec[k]
29         temp.key = rec[k - 1].key;
30         int i = k;//指向当前节点
31         int j = 2 * k;//指向左子树根节点
32         
33         while(j <= end){
34             if(j < end && rec[j - 1].key > rec[j].key)//这里j要小于end
35                 j = j + 1;//找到左右子树节点最小值得下标
36             if(temp.key < rec[j - 1].key)//这里用的是temp,不是rec[k]，因为上移的时候会覆盖掉rec[k]的值
37                 break;//说明满足堆的性质，不用调整
38             else{
39                 rec[i - 1].key = rec[j - 1].key;//子节点上移
40                 i = j;
41                 j = 2 * i;
42             }
43         }
44         rec[i - 1].key = temp.key;//调整完后，将暂存的内容放到当前节点中
45     }
46     
47     /**
48      * 对数组rec[]按关键字key堆排序
49      * 1.建堆
50      * 2.交换最后一个元素和堆顶元素，调整堆，重复执行n - 1次
51      * @param rec
52      */
53     public void heapSort(Rec rec[]){
54         int n = rec.length;
55         for(int i = n / 2; i >= 1; i--){
56             shift(rec, i , n);
57         }//建堆
58         System.out.println("建堆之后：");
59         this.rec.showArray(rec);
60         for(int i = 1; i < n; i++){
61             Rec temp = new Rec();
62             temp.key = rec[0].key;
63             rec[0].key = rec[n - i].key;
64             rec[n - i].key = temp.key;//交换堆顶和最后一个元素
65             
66             shift(rec, 1 , n - i);//调整第一个元素
67             System.out.println("第" + i + "趟，完成后：");
68             this.rec.showArray(rec);
69         }
70     }
71 }

Rec.java

package com.gxf.heapsort;

public class Rec {
    public int key;
    
    public Rec(int key){
        this.key = key;
    }
    public Rec(){
        
    }
    public void showArray(Rec rec[]){
        for(int i = 0; i < rec.length ; i++){
            
            System.out.print(rec[i].key + " ");
        }
        System.out.println();
    }
    public Rec[] getRecArray(int array[]){
        Rec result[] = new Rec[array.length];
        for(int i = 0; i < array.length; i++){
            result[i] =  new Rec(array[i]);
        }
        return result;
    }
}

Test.java

 1 package com.gxf.heapsort;
 2 
 3 
 4 
 5 public class Test {
 6     public static void main(String args[]){
 7         Rec rec = new Rec();
 8         HeapSort heapSort = new HeapSort();
 9         
10         int array[] = new int[]{0, 32, 1, 34, 54, 5, 6};
11         Rec array_rec[] = rec.getRecArray(array);
12         System.out.println("使用堆排序之前的顺序：");
13         rec.showArray(array_rec);
14         
15         heapSort.heapSort(array_rec);//堆排序
16         
17         System.out.println("使用堆排序之后：");
18         rec.showArray(array_rec);
19     }
20 }

ps:这里调程序的时候我将建堆后和每次调整的结果都打印出来了