堆排序
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：
- 1.大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
- 2.小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；
堆排序的平均时间复杂度为 Ο(nlogn)。
1. 算法步骤
- 1.将待排序序列构建成一个堆 H[0……n-1]，根据（升序降序需求）选择大顶堆或小顶堆；
- 2.把堆首（最大值）和堆尾互换；
- 3.把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
- 4.重复步骤 2，直到堆的尺寸为 1。
2. 动图演示
动图演示
3. JavaScript 代码实现
1
var len; // 因为声明的多个函数都需要数据长度，所以把len设置成为全局变量
2
3
function buildMaxHeap(arr) { // 建立大顶堆
4
len = arr.length;
5
for (var i = Math.floor(len/2); i >= 0; i--) {
6
heapify(arr, i);
7
}
8
}
9
10
function heapify(arr, i) { // 堆调整
11
var left = 2 * i + 1,
12
right = 2 * i + 2,
13
largest = i;
14
15
if (left < len && arr[left] > arr[largest]) {
16
largest = left;
17
}
18
19
if (right < len && arr[right] > arr[largest]) {
20
largest = right;
21
}
22
23
if (largest != i) {
24
swap(arr, i, largest);
25
heapify(arr, largest);
26
}
27
}
28
29
function swap(arr, i, j) {
30
var temp = arr[i];
31
arr[i] = arr[j];
32
arr[j] = temp;
33
}
34
35
function heapSort(arr) {
36
buildMaxHeap(arr);
37
38
for (var i = arr.length-1; i > 0; i--) {
39
swap(arr, 0, i);
40
len--;
41
heapify(arr, 0);
42
}
43
return arr;
44
}
Copied!
4. Python 代码实现
1
def buildMaxHeap(arr):
2
import math
3
for i in range(math.floor(len(arr)/2),-1,-1):
4
heapify(arr,i)
5
6
def heapify(arr, i):
7
left = 2*i+1
8
right = 2*i+2
9
largest = i
10
if left < arrLen and arr[left] > arr[largest]:
11
largest = left
12
if right < arrLen and arr[right] > arr[largest]:
13
largest = right
14
15
if largest != i:
16
swap(arr, i, largest)
17
heapify(arr, largest)
18
19
def swap(arr, i, j):
20
arr[i], arr[j] = arr[j], arr[i]
21
22
def heapSort(arr):
23
global arrLen
24
arrLen = len(arr)
25
buildMaxHeap(arr)
26
for i in range(len(arr)-1,0,-1):
27
swap(arr,0,i)
28
arrLen -=1
29
heapify(arr, 0)
30
return arr
Copied!
5. Go 代码实现
1
func heapSort(arr []int) []int {
2
arrLen := len(arr)
3
buildMaxHeap(arr, arrLen)
4
for i := arrLen - 1; i >= 0; i-- {
5
swap(arr, 0, i)
6
arrLen -= 1
7
heapify(arr, 0, arrLen)
8
}
9
return arr
10
}
11
12
func buildMaxHeap(arr []int, arrLen int) {
13
for i := arrLen / 2; i >= 0; i-- {
14
heapify(arr, i, arrLen)
15
}
16
}
17
18
func heapify(arr []int, i, arrLen int) {
19
left := 2*i + 1
20
right := 2*i + 2
21
largest := i
22
if left < arrLen && arr[left] > arr[largest] {
23
largest = left
24
}
25
if right < arrLen && arr[right] > arr[largest] {
26
largest = right
27
}
28
if largest != i {
29
swap(arr, i, largest)
30
heapify(arr, largest, arrLen)
31
}
32
}
33
34
func swap(arr []int, i, j int) {
35
arr[i], arr[j] = arr[j], arr[i]
36
}
Copied!
6. Java 代码实现
1
public class HeapSort implements IArraySort {
2
3
@Override
4
public int[] sort(int[] sourceArray) throws Exception {
5
// 对 arr 进行拷贝，不改变参数内容
6
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
7
8
int len = arr.length;
9
10
buildMaxHeap(arr, len);
11
12
for (int i = len - 1; i > 0; i--) {
13
swap(arr, 0, i);
14
len--;
15
heapify(arr, 0, len);
16
}
17
return arr;
18
}
19
20
private void buildMaxHeap(int[] arr, int len) {
21
for (int i = (int) Math.floor(len / 2); i >= 0; i--) {
22
heapify(arr, i, len);
23
}
24
}
25
26
private void heapify(int[] arr, int i, int len) {
27
int left = 2 * i + 1;
28
int right = 2 * i + 2;
29
int largest = i;
30
31
if (left < len && arr[left] > arr[largest]) {
32
largest = left;
33
}
34
35
if (right < len && arr[right] > arr[largest]) {
36
largest = right;
37
}
38
39
if (largest != i) {
40
swap(arr, i, largest);
41
heapify(arr, largest, len);
42
}
43
}
44
45
private void swap(int[] arr, int i, int j) {
46
int temp = arr[i];
47
arr[i] = arr[j];
48
arr[j] = temp;
49
}
50
51
}
Copied!
7. PHP 代码实现
1
function buildMaxHeap(&$arr)
2
{
3
global $len;
4
for ($i = floor($len/2); $i >= 0; $i--) {
5
heapify($arr, $i);
6
}
7
}
8
9
function heapify(&$arr, $i)
10
{
11
global $len;
12
$left = 2 * $i + 1;
13
$right = 2 * $i + 2;
14
$largest = $i;
15
16
if ($left < $len && $arr[$left] > $arr[$largest]) {
17
$largest = $left;
18
}
19
20
if ($right < $len && $arr[$right] > $arr[$largest]) {
21
$largest = $right;
22
}
23
24
if ($largest != $i) {
25
swap($arr, $i, $largest);
26
heapify($arr, $largest);
27
}
28
}
29
30
function swap(&$arr, $i, $j)
31
{
32
$temp = $arr[$i];
33
$arr[$i] = $arr[$j];
34
$arr[$j] = $temp;
35
}
36
37
function heapSort($arr) {
38
global $len;
39
$len = count($arr);
40
buildMaxHeap($arr);
41
for ($i = count($arr) - 1; $i > 0; $i--) {
42
swap($arr, 0, $i);
43
$len--;
44
heapify($arr, 0);
45
}
46
return $arr;
47
}
Copied!
Last modified 2yr ago