算法-排序-堆

算法-排序

5 堆排序

特点

  • 不稳定
  • 较难理解(一时的)

简介

堆排序,顾名思义,用”堆”(完全二叉树)来排序.

堆又分两种:小根堆(分支节点小于它的子节点)(降序)、大根堆(分支节点大于它的子节点)(升序).

经过实验得知,完全二叉树的最后一个分支节点是n / 2 - 1.

演示

原始数据(8个)
7 4 8 3 2 5 1 6

1
2
3
4
       7
4 8
3 2 5 1
6

建堆

从下至上,依次调整分支节点

i = 3

1
2
3
4
       7
4 8
3 2 5 1
6

i = 2

1
2
3
4
       7
4 1
3 2 5 8
6

i = 1

1
2
3
4
       7
2 1
3 4 5 8
6

i = 0

1
2
3
4
       1
2 5
3 4 5 8
6

排序(出堆)

首尾交换,调整根节点

i = 7

1
2
3
4
        2
3 5
6 4 7 8
(1)

i = 6

1
2
3
4
        3
4 5
6 8 7 (2)
(1)

i = 5

1
2
3
4
        4
6 5
7 8 (3) (2)
(1)

i = 4

1
2
3
4
       5
6 8
7 (4) (3) (2)
(1)

i = 3

1
2
3
4
         6
7 8
(5) (4) (3) (2)
(1)

i = 2

1
2
3
4
          7
8 (6)
(5) (4) (3) (2)
(1)

i = 1

1
2
3
4
          8
(7) (6)
(5) (4) (3) (2)
(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
//在有n个节点的堆中调整第k个节点
void HeapShift(int array[], int n, int k)
{
while(k * 2 + 1 < n) //为分支节点(有孩子)
{
int child = k * 2 + 1; //左右孩子的最小值的下标,默认为左孩子的下标
if(child + 1 < n && array[child + 1] < array[child]) //有右孩子,且比左孩子小
{
child++; //更新左右孩子的最小值的下标为右孩子的下标
}
if(array[child] > array[k]) //左右孩子的最小值比父大(调整完毕)
{
return; //结束
}
swap(array[child], array[k]); //交换
k = child; //调整下一个
}
}

void Sort(int array[], int n)
{
//建堆:从下至上依次调整分支节点
for(int i = n / 2 - 1; i >= 0; i--)
{
HeapShift(array, n, i);
}
//排序(出堆):首尾交换,调整根节点
for(int i = n - 1; i > 0; i--)
{
swap(array[0], array[i]);
HeapShift(array, i, 0);
}
}

END

堆排序理解起来可能有点困难,需要你多用数据模拟几次.

接下来还有桶、希尔排序等.