一. 堆排序

堆排序是利用最大堆的性质进行的选择排序. 堆排序具有如下特点:

1) 时间复杂度O(nlogn)

2) 原址排序(就地排序): 在排序时把原序列分为堆区和非堆区两个区域, 堆区在前. 每次从堆区弹出一个元素并和非堆区的第一个元素交换, 直至堆区消失.

3) 不稳定排序

堆排序很简单, 所需的操作有:

1: void heapsort(vector
    
     & src);
    

2: inline int left(int i) { return (i << 1) + 1; }

3: void adjustDown(vector
    
     & src, int id, int heapsize);
    

二. 堆排序的过程

1. 节点的下沉操作

1: void adjustDown(vector
    
     & src, int id, int heapsize)
    

2: {

3: 	int child;

4:

5: 	for (; left(id) < heapsize; id = child)

6: 	{

7: 		// 找出最小的子结点

8: 		child = left(id);

9: 		if (child < heapsize - 1 && src[child] < src[child + 1])

10: 			++child;

11: 		// 如果父节点比子结点还小, 就让父节点下沉

12: 		if (src[id] < src[child])

13: 			swap(src[id], src[child]);

14: 		else break;

15: 	}

16: }

2. 原址建堆和弹堆操作

void heapsort(vector
     
      & src){    // 原址建堆. 把整个数组变成堆    for (int i = (src.size() >> 1) - 1; i >= 0; --i)    {        adjustDown(src, i, src.size());    }    // 弹出最大元素, 交换到堆区末尾(非堆区第一个元素)    for (int j = src.size() - 1; j > 0; --j)    {        swap(src[0], src[j]);  //deleteMax        adjustDown(src, 0, j);    }}