堆排序（Heap Sort）

堆排序（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]与无序区最后一个元素R[n-1]交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

算法分析

最佳情况：T(n) = O(nlogn)
最差情况：T(n) = O(nlogn)
平均情况：T(n) = O(nlogn)

代码实现

Java

Java 实现
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
import java.util.Arrays;

public class HeapSort {

    public static void maxHeapDown(int[] arr, int current, int size) {
        int max = current;
        int left = current * 2 + 1;
        int right = left + 1;
        if (left <= size && arr[max] < arr[left]) {
            max = left;
        }
        if (right <= size && arr[max] < arr[right]) {
            max = right;
        }
        if (max != current) {
            int temp = arr[max];
            arr[max] = arr[current];
            arr[current] = temp;
            maxHeapDown(arr, max, size);
        }
    }

    public static void heapSortAsc(int[] arr, int size) {
        for (int i = size / 2 - 1; i >= 0; i--) {
            maxHeapDown(arr, i, size - 1);
        }
        System.out.println(Arrays.toString(arr));
        for (int i = size - 1; i > 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            maxHeapDown(arr, 0, i - 1);
            System.out.println(Arrays.toString(arr));
        }
    }

    public static void main(String[] args) {
        int[] arr = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
        System.out.printf("原始数组：%s\n", Arrays.toString(arr));
        heapSortAsc(arr, arr.length);
        System.out.printf("排序后数组：%s\n", Arrays.toString(arr));
    }
}

Python

Python 实现
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
def max_heap_down(arr, current, size):
    max = current
    left = current * 2 + 1
    right = left + 1
    if left <= size and arr[max] < arr[left]:
        max = left
    if right <= size and arr[max] < arr[right]:
        max = right
    if max != current:
        arr[max], arr[current] = arr[current], arr[max]
        max_heap_down(arr, max, size)


def heap_sort_asc(arr, size):
    for i in range(int(size / 2 - 1), -1, -1):
        max_heap_down(arr, i, size - 1)
    print(arr)
    for i in range(size - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        max_heap_down(arr, 0, i - 1)
        print(arr)


if __name__ == '__main__':
    arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
    print('原始数组：', arr)
    heap_sort_asc(arr, len(arr))
    print('排序后数组：', arr)

Go

Go 实现
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
package main

import (
    "fmt"
)

func MaxHeapDown(arr []int, current, size int) { // 最大堆
    max := current                            // 假设最大值的索引就是当前的根节点索引
    left := current*2 + 1                     // 左节点
    right := left + 1                         // 右节点
    if left <= size && arr[max] < arr[left] { // 左子节点大于父节点
        max = left
    }
    if right <= size && arr[max] < arr[left+1] { // 右子节点大于父节点
        max = right
    }
    if max != current { // 经过上面两步 if 判断，找出两个子节点中的最大的并且大于父节点的子节点
        arr[max], arr[current] = arr[current], arr[max]
        MaxHeapDown(arr, max, size)
    }
}

func HeapSortAsc(arr []int, size int) {
    for i := size/2 - 1; i >= 0; i-- { // 遍历完得到的数组实际上是一个大根堆
        MaxHeapDown(arr, i, size-1)
    }
    fmt.Println(arr)
    for i := size - 1; i > 0; i-- { // 从最后一个元素开始对序列进行调整，不断的缩小调整的范围直到第一个元素
        arr[0], arr[i] = arr[i], arr[0] // 大根堆，第一个数最大，将其和最后一个数交换，此时最大值在数组的最后面
        MaxHeapDown(arr, 0, i-1)        // 经过上面的交换，a[0...i-1]，可能已经不是大根堆，所以需要重新排序成大根堆
        fmt.Println(arr)
    }
}

func main() {
    arr := []int{3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48}
    fmt.Printf("原始数组：%v\n", arr)
    HeapSortAsc(arr, len(arr))
    fmt.Printf("排序后数组：%v\n", arr)
}