堆排序

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法:

  1. 大顶堆:每个节点的值都大于或等于其子节点的值,在堆排序算法中用于升序排列;
  2. 小顶堆:每个节点的值都小于或等于其子节点的值,在堆排序算法中用于降序排列;

堆排序的平均时间复杂度为 Ο(nlogn)。

1. 算法步骤

  1. 将待排序序列构建成一个堆 H[0……n-1],根据(升序降序需求)选择大顶堆或小顶堆;

  2. 把堆首(最大值)和堆尾互换;

  3. 把堆的尺寸缩小 1,并调用 shift_down(0),目的是把新的数组顶端数据调整到相应位置;

  4. 重复步骤 2,直到堆的尺寸为 1。

2. 动图演示

动图演示

3. JavaScript 代码实现

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
var len;    // 因为声明的多个函数都需要数据长度,所以把len设置成为全局变量

function buildMaxHeap(arr) { // 建立大顶堆
len = arr.length;
for (var i = Math.floor(len/2); i >= 0; i--) {
heapify(arr, i);
}
}

function heapify(arr, i) { // 堆调整
var left = 2 * i + 1,
right = 2 * i + 2,
largest = i;

if (left < len && arr[left] > arr[largest]) {
largest = left;
}

if (right < len && arr[right] > arr[largest]) {
largest = right;
}

if (largest != i) {
swap(arr, i, largest);
heapify(arr, largest);
}
}

function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

function heapSort(arr) {
buildMaxHeap(arr);

for (var i = arr.length-1; i > 0; i--) {
swap(arr, 0, i);
len--;
heapify(arr, 0);
}
return arr;
}

4. 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
29
30
def buildMaxHeap(arr):
import math
for i in range(math.floor(len(arr)/2),-1,-1):
heapify(arr,i)

def heapify(arr, i):
left = 2*i+1
right = 2*i+2
largest = i
if left < arrLen and arr[left] > arr[largest]:
largest = left
if right < arrLen and arr[right] > arr[largest]:
largest = right

if largest != i:
swap(arr, i, largest)
heapify(arr, largest)

def swap(arr, i, j):
arr[i], arr[j] = arr[j], arr[i]

def heapSort(arr):
global arrLen
arrLen = len(arr)
buildMaxHeap(arr)
for i in range(len(arr)-1,0,-1):
swap(arr,0,i)
arrLen -=1
heapify(arr, 0)
   return arr

5. 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
func heapSort(arr []int) []int {
4arrLen := len(arr)
4buildMaxHeap(arr, arrLen)
4for i := arrLen - 1; i >= 0; i-- {
44swap(arr, 0, i)
44arrLen -= 1
44heapify(arr, 0, arrLen)
4}
4return arr
}

func buildMaxHeap(arr []int, arrLen int) {
4for i := arrLen / 2; i >= 0; i-- {
44heapify(arr, i, arrLen)
4}
}

func heapify(arr []int, i, arrLen int) {
4left := 2*i + 1
4right := 2*i + 2
4largest := i
4if left < arrLen && arr[left] > arr[largest] {
44largest = left
4}
4if right < arrLen && arr[right] > arr[largest] {
44largest = right
4}
4if largest != i {
44swap(arr, i, largest)
44heapify(arr, largest, arrLen)
4}
}

func swap(arr []int, i, j int) {
4arr[i], arr[j] = arr[j], arr[i]
}

6. 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
44
45
46
47
48
49
50
51
public class HeapSort implements IArraySort {

@Override
public int[] sort(int[] sourceArray) throws Exception {
// 对 arr 进行拷贝,不改变参数内容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

int len = arr.length;

buildMaxHeap(arr, len);

for (int i = len - 1; i > 0; i--) {
swap(arr, 0, i);
len--;
heapify(arr, 0, len);
}
return arr;
}

private void buildMaxHeap(int[] arr, int len) {
for (int i = (int) Math.floor(len / 2); i >= 0; i--) {
heapify(arr, i, len);
}
}

private void heapify(int[] arr, int i, int len) {
int left = 2 * i + 1;
int right = 2 * i + 2;
int largest = i;

if (left < len && arr[left] > arr[largest]) {
largest = left;
}

if (right < len && arr[right] > arr[largest]) {
largest = right;
}

if (largest != i) {
swap(arr, i, largest);
heapify(arr, largest, len);
}
}

private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

}

7. PHP 代码实现

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
function buildMaxHeap(&$arr)
{
global $len;
for ($i = floor($len/2); $i >= 0; $i--) {
heapify($arr, $i);
}
}

function heapify(&$arr, $i)
{
global $len;
$left = 2 * $i + 1;
$right = 2 * $i + 2;
$largest = $i;

if ($left < $len && $arr[$left] > $arr[$largest]) {
$largest = $left;
}

if ($right < $len && $arr[$right] > $arr[$largest]) {
$largest = $right;
}

if ($largest != $i) {
swap($arr, $i, $largest);
heapify($arr, $largest);
}
}

function swap(&$arr, $i, $j)
{
$temp = $arr[$i];
$arr[$i] = $arr[$j];
$arr[$j] = $temp;
}

function heapSort($arr) {
global $len;
$len = count($arr);
buildMaxHeap($arr);
for ($i = count($arr) - 1; $i > 0; $i--) {
swap($arr, 0, $i);
$len--;
heapify($arr, 0);
}
return $arr;
}
扫码加我微信