C++堆排序算法的实现方法

时间:2022-06-22 06:43:17

 本文实例讲述了C++实现堆排序算法的方法,相信对于大家学习数据结构与算法会起到一定的帮助作用。具体内容如下:

 首先,由于堆排序算法说起来比较长,所以在这里单独讲一下。堆排序是一种树形选择排序方法,它的特点是:在排序过程中,将L[n]看成是一棵完全二叉树的顺序存储结构,利用完全二叉树中双亲节点和孩子节点之间的内在关系,在当前无序区中选择关键字最大(或最小)的元素。

一、堆的定义

堆的定义如下:n个关键字序列L[n]成为堆,当且仅当该序列满足:
①L(i) <= L(2i)且L(i) <= L(2i+1)  或者  ②L(i) >= L(2i)且L(i) >= L(2i+1)   其中i属于[1, n/2]。

满足第①种情况的堆称为小根堆(小顶堆),满足第②种情况的堆称为大根堆(大顶堆)。在大根堆中,最大元素存放在根结点中,且对任一非根结点,它的值小于或等于其双亲结点值。小根堆则恰恰相反,小根堆的根结点存放的是最小元素。例如{16, 14, 10, 8, 7, 9, 3, 2}表示的大根堆:

                          C++堆排序算法的实现方法       

二、构造初始堆

堆排序的关键就是构造初始堆。n个结点的完全二叉树中,最后一个结点是第n/2(向下取整)个结点的孩子。所以构造初始堆的流程是:对第n/2(向下取整)个结点为根的子树进行筛选(以大根堆为例,若根结点的关键字小于左右子女中关键字的较大者,则交换),使该子树成为堆。之后向前依次对从n/2-1到1的各结点为根的子树进行筛选,看该结点值是否大于其左右子结点的值,若不是,将左右子结点中较大值与之交换,交换后可能会破坏下一级的堆,于是继续采用上述方法构造下一级的堆,直到以该结点为根的子树构成堆为止。反复利用上述调整堆的方法建堆,直到根结点。

由于在数组中下标从0开始,所以在堆中i的左子结点为2*i+1,右子结点为2*i+2。下面是将某个结点i向下调整建堆的算法实现:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void AdjustDown(ElementType A[], int i, int len)
{
  ElementType temp = A[i]; // 暂存A[i]
   
  for(int largest=2*i+1; largest<len; largest=2*largest+1)
  {
    if(largest!=len-1 && A[largest+1]>A[largest])
      ++largest;     // 如果右子结点大
    if(temp < A[largest])
    {
      A[i] = A[largest];
      i = largest;     // 记录交换后的位置
    }
    else
      break;
  }
  A[i] = temp;  // 被筛选结点的值放入最终位置
}
 

建堆,从n/2(向下取整)到1依次对各结点向下调整,当然由于数组下标从0开始,所以:

?
1
2
3
4
5
void BuildMaxHeap(ElementType A[], int len)
{
  for(int i=len/2-1; i>=0; --i) // 从i=n/2-1到0,反复调整堆
    AdjustDown(A, i, len);
}

三、堆排序

构造初始堆成功以后,堆排序的思路就很简单了:首先将存放在L[n]中的n个元素建成初始堆,由于堆本身的特点(以大根堆为例),堆顶元素就是最大值。输出堆顶元素后,通常将堆底元素送入堆顶,此时根结点已不满足大根堆的性质,堆被破坏。这时将堆顶元素向下调整使其继续保持大根堆的性质,再输出堆顶元素。如此重复,直到堆中仅剩下一个元素为止。算法实现如下:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
void HeapSort(ElementType A[], int n)
{
  BuildMaxHeap(A, n);    // 初始建堆
  for(int i=n-1; i>0; --i) // n-1趟的交换和建堆过程 
  {
    // 输出最大的堆顶元素(和堆底元素交换)
    A[0] = A[0]^A[i];
    A[i] = A[0]^A[i];
    A[0] = A[0]^A[i];
    // 调整,把剩余的n-1个元素整理成堆
    AdjustDown(A, 0, i);  
  }
}

四、性能分析

时间复杂度:向下调整的时间与树高有关,为O(h)。可以证明在元素个数为n的序列上建堆,其时间复杂度为O(n)。之后还有n-1次向下调整操作,每次调整的时间为O(h),故在最好,最坏和平均情况下,堆排序的时间复杂度为O(nlogn)。

空间复杂度:仅使用了常数个辅助单元,空间复杂度为O(1)。

稳定性:不稳定。