排序算法——堆排序

概述

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆的性质:即子节点的键值或索引总是小于(或者大于)它的父节点。如果要从大到小排序,则应该使用大根堆,即根节点的值最大。时间复度为\(O(nlog(n))\).


步骤

  • 建堆(最大堆),常采用向上调整建堆
  • 将堆第一个元素与已排好数据前一位交换,进行下沉操作调整堆,同时乱序数据量减少一个
  • 直到所有数据排序完成

可以看出,堆排序也是选择排序的一种,通过大小根堆的性质一步步挑选出最值,然后完成排序。用堆取最值的时间复杂度为\(O(logn)\),所用元素都遍历一遍为\(O(n)\),总时间复杂度为\(O(nlog(n))\)


示例代码

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
public class HeapSort {
public static void main(String[] args) {
int[] arr = {57, 65, 54, 30, 45, 7, 6, 26, 35, 96};
int[] arr_new = heapSort(arr);
for (int i : arr_new) {
System.out.println(i);
}
}

public static int[] heapSort(int[] a) {
int[] arr = builtHeap(a);
int index = arr.length - 1;
while (index > 0) {
swap(arr, index);
index--;
}
return arr;

}

public static int[] builtHeap(int[] arr) {
int len = arr.length;
int[] temp = new int[len];
for (int i = 0; i < len; i++) {
temp[i] = arr[i];
swim(temp, i);
}
return temp;
}

public static void swim(int[] arr, int index) {
if (index == 0) {
return;
}
while (arr[index] > arr[(index - 1) / 2]) {
int t = arr[index];
arr[index] = arr[(index - 1) / 2];
arr[(index - 1) / 2] = t;
index = (index - 1) / 2;
}
}

public static void swap(int[] arr, int index) {
int t = arr[0];
arr[0] = arr[index];
arr[index] = t;
sink(arr, index);
}

public static void sink(int[] arr, int index) {
int i1 = 0;
int i2 = 0;
while ((2 * i1 + 1) < index) {
i2 = 2 * i1 + 1;
if ((2 * i1 + 2) < index) {
if (arr[2 * i1 + 1] > arr[2 * i1 + 2]) {
i2 = 2 * i1 + 1;
} else {
i2 = 2 * i1 + 2;
}
}
if (arr[i1] < arr[i2]) {
int t = arr[i1];
arr[i1] = arr[i2];
arr[i2] = t;
i1 = i2;
} else {
break;
}
}
}


}
[out]:
6
7
26
30
35
45
54
57
65
96

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
def heapSort(arr):
arr = builtHeap(arr)
index = len(arr) - 1
while index > 0:
swap(arr, index)
index -= 1

return arr


def sink(arr, index): # 结束于index-1
i1 = 0
while (2 * i1 + 1) < index:
i2 = 2 * i1 + 1
if 2 * i1 + 2 < index:
if arr[2 * i1 + 1] > arr[2 * i1 + 2]:
i2 = 2 * i1 + 1
else:
i2 = 2 * i1 + 2
if arr[i1] < arr[i2]:
arr[i1], arr[i2] = arr[i2], arr[i1]
i1 = i2
else:
break


def swim(arr, index):
while arr[index] > arr[max((index - 1) // 2, 0)]:
arr[index], arr[(index - 1) // 2] = arr[(index - 1) // 2], arr[index]
index = (index - 1) // 2


def swap(arr, index):
arr[0], arr[index] = arr[index], arr[0]
sink(arr, index)


def builtHeap(arr):
length = len(arr)
temp = [0] * length
for i in range(len(arr)):
temp[i] = arr[i]
swim(temp, i)

return temp


if __name__ == '__main__':
a = [59, 56, 97, 19, 40, 48, 13, 75, 51, 65]
out = heapSort(a)
print(out)

[out]:
[13, 19, 40, 48, 51, 56, 59, 65, 75, 97]