堆排序.txt

c语言排序

 Espate studio


--------------------------------------------------------------------------------

堆排序

定义：

   n个元素的序列{k1,k2,...,kn}当且满足下列关系时，称之为堆。

ki<=k2i ,ki<=k2i+1 或ki>=k2i ,ki>=k2i+1

（i=1,2,...,|-n/2-|）

   若将和此序列对应的以为数组看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不大于其左，右孩子结点值。由此若序列{k1,k2,...,kn}是堆，则堆顶元素（或完全二叉树的根）必是序列中最小或最大值。
 若在输出堆顶元素后，使得剩余n-1个元素的序列重建成一个堆，则得到n个元素中的次小值。如此反复执行，便能得到一个有序的序列，这个过程就叫做堆排序。

讨论

  实现堆排序的两个主要问题：
            （1）如何由一个无序的序列建成一个堆？
            （2）如何在输出堆顶元素之后，调整剩余元素成为一个新的堆

首先讨论（2）下图是一个堆的示例，则变化如下由图a到图c

    图a

图b

图c

  得到次小值11，所以我们的算法是(设m指向堆尾，s指向要调整的结点）：
    （1）图a-->图b,堆首与堆尾交换，m减一
    （2）图b-->图c,结点83(即ks)与结点27( k2s）,结点11（k2s+1）比较（从二叉树角度看是与其左、右兄弟比较）并与
         较小者交换，使s等于较小者的序列号。否则不用调整
    （3）重复步骤（2）

   参考程序：（执行步骤（2））

typedef int HeapType;
void HeapAdjust(HeapType * & h,int s,int m)
{
     int temp;
     int j;
     temp=h[s];
     j=2*s;
     while (j<=m)
     {
          if (h[j]>h[j+1]&&j<m) j++;
          if (temp<h[j]) break;
          h[s]=h[j];
          s=j;
          j=j*2;
     }
     h[s]=temp;
}

而由一个无序的序列建成一个堆可利用上述程序

参考程序：（由一个无序的序列建成一个堆）

void HeapSetUp(HeapType * & h,int n)
{
   for(int i=n/2;i>0;i--)
      HeapAdjust(h,i,n);
}

实现堆排序：

    结合定义及上述讨论很容易给出下面的程序：

void HeapSort(HeapType * & h,int n)
{
     int t;
     HeapSetUp(h,n);
     for(int i=n;i>1;i--)
     {
          t=h[i];
          h[i]=h[1];
          h[1]=t;
          HeapAdjust(h,1,i-1);
     }
}

    adiwei