堆排序

发表于 | 分类于

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

算法描述

  • 将初始待排序关键字序列(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，则整个排序过程完成。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
public class HeapSort{
     //声明全局变量，用于记录数组array的长度；
     static int len;
     
    /**
     * 堆排序算法
     * @param array
     * @return
     */
    public static int[] heapSort(int[] array){
        len = array.length;
        if (len<1){
            return array;
        }
        //1、构建一个大根堆
        buildMaxHeap(array);
        //2、循环将堆首位（最大值）与末位交换，然后再重新调整最大堆
        while (len>0){
            swap(array,0,len-1);
            len--;
            adjustHeap(array,0);
        }
        return array;
    } 
    /**
     * 建立最大堆
     * @param array
     */
    public static void buildMaxHeap(int[] array){
        //从最后一个非叶子节点开始向上构造最大堆
        for (int i = (len-1)/2;i>=0;i--){
            adjustHeap(array,i);
        }
    }
    /**
     * 调整使其成为大根堆
     * @param array
     * @param i
     */
    public static void adjustHeap(int[] array,int i){
        int maxIndex = i;
        //如果有左子树，且左子树大于父节点，则将最大指针指向左子树
        if (i*2<len&&array[i*2]>array[maxIndex]){
            maxIndex = i*2;
        }
        //如果有右子树，且右子树大于父节点，则将最大指针指向右子树
        if (i*2+1<len&&array[i*2+1]>array[maxIndex]){
            maxIndex = i * 2 + 1;
        }
        //如果父节点不是最大值，则将父节点与最大值交换，并且递归调整与父节点交换的位置。
        if (maxIndex != i) {
            swap(array, maxIndex, i);
            adjustHeap(array, maxIndex);
        }

    }
    private static void swap(int[] array,int pre,int next){
        int temp;
        temp=array[pre];
        array[pre]=array[next];
        array[next]=temp;
    }
    public static void main(String[] args) {
        int[] array = new int[]{6,3,8,2,9,1};
        System.out.println(Arrays.toString(heapSort(array)));
    }       
}

算法分析

  • 时间效率：时间效率：O(nlog2n)
  • 空间效率：O（1）
  • 稳 定 性：不稳定
    适用于n 较大的情况