算法-排序-堆

算法-排序

5 堆排序

特点

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

简介

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

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

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

演示

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

       7
    4     8
  3  2  5  1
6  

建堆

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

i = 3

       7
    4     8
  3  2  5  1
6  

i = 2

       7
    4     1
  3  2  5  8
6  

i = 1

       7
    2    1
  3  4  5  8
6  

i = 0

       1
    2    5
  3  4  5  8
6  

排序(出堆)

首尾交换，调整根节点

i = 7

        2
     3    5
   6  4  7  8
(1)

i = 6

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

i = 5

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

i = 4

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

i = 3

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

i = 2

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

i = 1

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

至此，数据已经变成有序.

实现

//在有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

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

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