经典排序算法归纳笔记(3)

7070阅读　0评论2014-04-30　wjlkoorey258
分类：C/C++

    这是排序算法的最后一篇了，剩下归并排序、堆排序和快速排序了，关于各种排序算法的效率、适用场合和性能的分析留到下一篇再讲。

归并排序
   归并排序是基于归并操作的，归并操作的思想很简单，针对两个已经排好序的有序序列：
   1、申请一块额外的存储空间，空间的大小等于两个待操作序列长度之和；
   2、设定两个指针，初始位置分别指向两个有序序列的开始处；
   3、比较两个指针所指元素的值，较小者放到合并空间里，同时指针向后移动；
   4、重复步骤3直到某个指针达到序列末尾；
   5、如果另外一个序列的指针为到达末尾，则将该序列里剩下的元素拷贝到合并空间的尾部。

   这便是归并操作的核心思想，其归并过程如下：

   我们看到一趟归并操作，要求参与归并的序列必须有序，如果参与归并操作的两个序列(即我们常见的两路归并)长度分别是M和N，则还需要额外M+N的辅助存储空间。归并排序的基本操作就是归并操作，所以归并排序其实是“分治策略”的第一个典型应用。将待排序序列拆分成两个等长序列，然后将每个子序列继续拆分，直到最后的子序列长度为1为止。然后对拆分后的子序列两两执行归并操作，最后就达到了归并排序的目的。所以说归并排序算法分两步：第一步是拆分，第二步是归并。还是以前面见到过的测试序列A={6,3,1,9,2,5,8,7,4}为例，先看一下其拆分过程：

   待排序最终被拆分成长度为1的子序列，然后对这些子序列两两执行归并操作。根据上述归并操作的思想，我们可以很容易写出归并操作的核心代码：

点击(此处)折叠或打开

  1. int merge_ops(int a[],int alen,int b[],int blen){
  2.         int i,j,k,len=alen+blen;
  3.         int ele_size = sizeof(int);
  4.         int *tmp = (int*)malloc(ele_size*len);              //为归并后的结果申请临时存储空间
  5.         if(NULL == tmp){
  6.             perror("Error!can't alloc mem!");
  7.             return -1;
  8.         }

  10.         memset(tmp,0,ele_size*len);                         //清空临时缓冲区

  12.         i=j=k=0;
  13.         while(i<alen && j<blen){                           
  14.                 tmp[k++] = ((a[i]<b[j]) ? a[i++]:b[j++]);  //执行归并过程
  15.         }

  17.         //将某一序列的剩余元素追加到归并后的存储空间里(如果有的话)
  18.         if(i>=alen && j<blen){                            
  19.                 memcpy(tmp+k,b+j,ele_size*(blen-j));
  20.         }
  21.         if(j>=blen && i<alen){
  22.                 memcpy(tmp+k,a+i,ele_size*(alen-i));
  23.         }

  25.         memcpy(a,tmp,ele_size*len);
  26.         free(tmp);
  27.         tmp = NULL;
  28.         return 0;
  29. }
    可以看到，上述归并操作的代码逻辑并不复杂，接下来我们需要完成归并排序的另一项工作，那就是拆分。我们要将待排序序列不断拆分，最终变成一个个长度为1的子序列，用于实现这个拆分过程最好的办法就是递归。因此，拆分的递归代码如下：

点击(此处)折叠或打开

  1. int merge(int a[],int len){
  2.     if(len == 1){          //当子序列长度为1时则停止拆分
  3.          return 0;
  4.     }

  6.     //拆分的过程
  7.     if(merge(a,len/2)<0)
  8.         return -1;
  9.     if(merge(a+len/2,len-len/2)<0)            
  10.         return -1;

  12.     //归并的过程
  13.     return merge_ops(a,len/2,a+len/2,len-len/2);
  14. }
    归并排序的效率还是蛮高的，它包含了“拆分”和“归并”两个过程。对于长度为n的待排序序列而言，将其拆分成长度是1的子序列时，如果拆分每一个元素所需要的时间为固定值C，那么拆分n个元素的时间总和就是Cn。在归并过程中，我们是在深度为log(n)+1的二叉树上执行的，二叉树每一层上的元素个数都是相同的，同样地，如果归并一个元素需要的时间为P，那么归并n个元素需要的时间总和就是Pn，即每一层都需要Pn的时间，所以归并log(n)+1层就需要Pn(log(n)+1)的时间。最后归并排序总耗费的时间：
T(n)=Cn+Pn(log(n)+1)=Pn*log(n)+(C+P)n，取C和P中较大者，假如记作M，则T(n)=Mn*log(n)+Mn。相比于nlog(n)来说，常数M和Mn可以忽略不计，所以可以得到归并排序的时间复杂度为O(nlog(n))。

堆排序
   排序算法里的堆和计算机进程地址空间里的堆并不是一个概念。堆又分二叉堆和N叉堆，其中二叉堆比较常见(目前我们只讨论这种，后面我们提到堆时默认情况下都指的是二叉堆)，是一个类似于完全二叉树的数据结构。堆排序主要是借助堆这种数据结构来实现的排序算法。堆的主要特性就是：父节点的值总是大于(或者小于)等于任意一个子节点的值。

   我们将父节点的值总是大于等于任意一个子节点的值的堆叫做大堆(或者大根堆)；同样地，父节点的值总是小于等于任意一个子节点的值的堆叫做小堆(或者小根堆)。

   通常情况下，堆都是用一维数组进行存储。编号为i的节点，其左子节点在数组中的下标为2×i+1，右子节点的下标为2×i+2；编号为i的子节点，其父节点的标号为(i-1)/2取整。例如：A={6,3,1,9,2,5,8,7,4}

   所以我们看到，堆排序的核心点是如何建立一个堆，这方面在STL里已经有很好的封装和实现了。当然，这里我们不是拿来主义，如果自己不对算法、原理本身进行研究，总感觉雾里看花似的。因为我是进行升序排列，所以需要建大根堆(小根堆原理一样)。可能有人会觉得应该建立小根堆才对，因为我们的堆是借助数组存储的，不使用树形结构，所以当堆调整成大根堆之后，将堆的根部元素依次和后面的叶子节点进行交换。然后再把堆调整成大根堆，依次循环下去，直到堆里仅剩一个元素为止。这样堆排序就完成了，且是原地排序，空间复杂度为O(1)。以上面的序列A为例，先看一下将其调整成大根堆的过程：
   如果序列的长度为n则我们需要从编号为(n/2)-1的元素开始调整，直到编号为0。因为对于编号为i(注意数组小标是i从0开始编号)的节点，其子节点的编号需要满足2*i+1    第一步时，index=3，所以其左右子节点的编号分别为7和8，在左右子节点a[7]和a[8]里找一个较大者，然后和a[3]进行比较。发现a[3]已经是三个参与比较的值中最大的了，因此这一步不用调整，index减1，后执行第二步，如下：



   如上所示，第二步时index=2，在根节点和两个子节点之间进行比较，将最大值交换到根节点上，如右所示；
   如上所示，第三步时index=1，最大值其左子节点a[3]=9，调整后的结果如右所示。节点a[1]=3的值“下沉”后我们发现它打破了原来左下角那个二叉树的平衡，所以接下来需要对其重新调整，使它满足大根堆的特性，过程如第四步所示：
   第四步调整时，index的值并没有改变，而是对index的左子节点所表示的二叉树进行了调整。当然，如果左子节点的任意一个子节点还是一棵二叉树，则需要一直递归调整下去，直到不需要调整或者遇到叶子节点为止。

    第五步时，index=0，调整后的结果如右所示。同样地，我们发现，根节点的左子节点“下沉”后也破坏原有二叉树的平衡性，因此需要继续调整：
    到此为止，我们的大根堆就算建立好，即任意一个节点如果有子节点，则根节点的值大于等于其左右子节点的值。
   根据上述建堆的过程，我们可以用递归算法来实现，但递归不方便理解，所以先看一个非递归的建堆过程：

点击(此处)折叠或打开

  1. //取得节点编号为i的左子节点的编号
  2. int leftChildIndex(int i){
  3.         return (2*i+1);
  4. }

  6. //取得节点编号为i的右子节点的编号
  7. int rightChildIndex(int i){
  8.         return (2*i+2);
  9. }

  10.
  11. //交换两个数
  12. void swap(int *a,int *b){
  13.         int t;
  14.         t = *a;
  15.         *a = *b;
  16.         *b = t;
  17. }

  19. /××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××
  20.  功能描述：AdjustHeap用于在堆里对编号为i的节点进行调整，使其满足大根堆的特性
  21.  输入参数: 
  22.           a  ：待排序的序列；
  23.           len：待排序序列长度；
  24.           i  ：要调整的节点编号
  25.  输出参数：无
  26.  返 回 值：无
  27.  ××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××/
  28. void AdjustHeap(int a[],int len,int i){
  29.         int left,right,bigger;
  30.         left = leftChildIndex(i);
  31.         right = rightChildIndex(i);

  32.
  33.         //如果i节点左右子节点编号均未越界才执行此循环
  34.         while(left<len || right<len){  
  35.             //如果右子节点编号未越界，则左子节点的下标也一定不会越界                    
  36.             if(right<len){                                  
  37.                 bigger = ((a[left]>a[right])?left:right);  //在左右子节点里找出较大者，将其编号用bigger标记
  38.             }else if(left<len){                            
  39.                 bigger = left;                           //如果右子节点越界，但左子节点未越界，则直接将左子节点标记为较大者
  40.             }else{                                                             
  41.                 break;                                  //否则的话，说明节点i是叶子节点，直接退出 
  42.             }

  43.
  44.             //如果编号为i的根节点的值，小于从其左右子节点里选出来的较大的值，则进行交换
  45.             if(a[bigger]>a[i]){
  46.                 swap(&a[i],&a[bigger]);

  47.
  48.                 i = bigger;             /*
  49.                                          交换完成后，用i标记新的较大者，即将i记为新的根节点，然后取其左右子节点重复迭代调整
  50.                                          如果把这个步骤改成递归算法，其实也不复杂
  51.                                          */
  52.                 left = leftChildIndex(i);
  53.                 right = rightChildIndex(i);
  54.             }else
  55.                 break;
  56.         }
  57. }
  58. /*******************************************************
  59.  功能描述：BuildHeap对长度为len的无序列a，将其构建成一个大根堆
  60.  输入参数：
  61.             a ：待排序的无序序列首地址
  62.             len：无序序列的长度
  63.  输出参数：无
  64.  返 回 值：无
  65.  *******************************************************/
  66. void BuildHeap(int a[],int len){
  67.      int i;
  68.      for(i=len/2-1;i>=0;i--){    //注意前面分析的为什么要从编号为n/2-1的元素开始依次递减进行调整
  69.          AdjustHeap(a,len,i);
  70.      }
  71. }

   当建好堆之后，堆排序的第一步就完成了。第二步就是不断的将堆的根元素交换到数组的末尾，然后重新再将堆调整成大根堆，并继续将堆的根元素继续和一维数组倒数第二个位的元素进行交换。一直这样下去，直到堆里剩下一个元素为止。还是看过程，下面是我们通过调用BuildHeap()将序列A建成的大根堆：
   我们将堆根元素和最后一个叶子元素4进行交换：
   因为此时，数组中的最后一个元素即堆的最末尾一个叶子元素已经被固定了，就相当于已经排好序了，所以在调整剩下来的大根堆时，序列的总长度要减1，即len=len-1，然后从堆的根元素开始调整，重新将其调整成大根堆，过程如下：

   然后再继续调整大根堆剩下来的部分，和上面的调整、排序流程是一模一样地：
   根据以上这个执行流程，现在我们就可以写出堆排序的核心代码了，非常简单、明了：

点击(此处)折叠或打开

  1. void heap_sort(int a[],int len){
  2.         int i;
  3.         BuildHeap(a,len);                //建堆

  5.         while(--len > 0){                //如果堆里仅剩下一个元素则停止排序
  6.                 swap(&a[0],&a[len]);     //从后向前，将堆的根节点和数组尾部依次执行交换
  7.                 AdjustHeap(a,len,0);     //交换完成后，再以堆的根节点作为参照，将堆重新调整成大根堆
  8.         }
  9. }

   堆排序的时间主要包含两部分：“建堆的时间”+“排序时调整堆的之间”。建堆和调整堆时我们都调用AdjustHeap()函数，这个函数会将根节点向下沉，且节点下沉的深度不会超过二叉树的深度，即log(n)+1，因此AdjustHeap()函数的时间复杂度为O(log(n))。在建堆的时候，我们一共执行了n/2-1次，也就是说调用了n/2-1次AdjustHeap()函数，还不明白这个n/2-1是如何来的童鞋强烈建议从头再认真、仔细看一遍。最后我们可以得出建堆的时间是(n/2-1)×log(n)，即建堆的时间复杂度为O(nlog(n))。
   那么堆排序的时候，根元素依次和叶子节点进行交换的时间为O(1)，主要的时间开销还在交换完成后重新调整堆上面。堆排序时一共需要交换n-1，也就是所执行过n-1次AdjustHeap()，所以在进行堆排序时所耗费的时间为(n-1)×log(n)，即排序时的时间复杂度同样为O(nlog(n))。因此，堆排序总的时间复杂度为O(nlog(n))。


快速排序
   快速排序本质上其实是对冒泡排序的一种改进，它和归并排序同样都是“分治策略”的一种典型应用。快速排序也分两个步骤：第一步，现将待排序序列依次拆分成子序列，然后在每个子序列上执行下述操作：
   1、两个指针分别指向序列的头和尾，且定义一个关键参考值=头指针所指向的元素的值；
   2、如果尾指针所指的元素值比头指针所指的元素值大，则尾指针向前移动，头指针不动；
   3、继续步骤2，如果尾指针所指的元素小于头指针所指的元素，且头、尾指针没有相遇，则将尾指针指向的元素值赋值给头指针所指向的元素值，同时头指针开始向头移动，尾指针不动；
   4、继续执行步骤3，如果头、尾指针相遇则程序停止，否则如果满足条件2则只习惯步骤2，否则继续执行步骤3.
   这样一趟快速排序下来后，所有比较关键参考值小得元素都在其左边，所有比它大的元素都在其右边了。然后在以关键参考值所在的位置为分界线，在分别对其左边和右边两个子序列重复执行这个过程，直到最后所有子序列的长度为1则停止。

    还是看一下序列A={6,3,1,9,2,5,8,7,4}的一趟快速排序过程：
   初始时我们选择key=a[low]=6作为关键参考元素，low指向a的头部，hight指向数组a的尾部，从后向前开始。
   第1步时，由于key>a[high]，所以a[low]=a[high]，然后low++；
   第2步时，由于a[low]    第3步和第2步一样；
   第4步时，a[low]>key，则执行a[high]=a[low]，然后high--；
   ... ... 
   这样一直下去直到第11步，当low和high相遇就停止，最后将a[low]=key，同时以low(或者以high也可以)为分界线对它的左右两个子序列重复执行刚才的操作，直到序列长度为1则停止。

   所以，我们现在可以写出一次快速排序的核心代码了：

点击(此处)折叠或打开

  1. int partoff(int a[],int low,int high)
  2. {
  3.     int key = a[low];   //取a[low]为关键参考元素
  4.     while(low<high)
  5.     {
  6.         while(low<high&&key<=a[high])       //从后向前找第一个比key小的元素
  7.               high--;
  8.         if(low<high)
  9.               a[low++] = a[high];          //找到后执行一次赋值，然后开始从前向后找

  11.         while(low<high && key >= a[low])  //从前先后找第一个比key大的元素
  12.               low++;
  13.         if(low<high)
  14.               a[high--] = a[low];        //找到后也执行一次赋值，然后再从后向前找
  15.     }

  16.
  17.     //如果low和high相遇，则退出上面的while循环，将key安放在low所指定的位置上，并返回low用于下一次拆分子序列时当参考定标
  18.     a[low] = key;
  19.     return low;
  20. }

    整个快速排序的过程就是不断调用上述函数的过程，那么采用递归的算法就很容易实现整个快速排序的过程了：

点击(此处)折叠或打开

  1. void quick_sort(int a[],int low,int high)
  2. {
  3.     int index=0;
  4.     if(low<high)
  5.     {
  6.         index = partoff(a,low,high);
  7.         quick_sort(a,low,index-1);
  8.         quick_sort(a,index+1,high);
  9.     }
  10. }

   快速排序是目前已知的内部(后面会解释内部排序)排序中效率比较高的排序算法。待排序序序列最终被拆分成深度为log(n)+1的二叉树，和前面的堆排序一样。
   第一次拆分时，总共的执行时间是Cn(C为固定的单位时间常数)；第二次拆分时，每个子序列的执行时间为Cn/2，一共两个子序列，则总的执行时间是Cn/2+Cn/2=Cn；第三次拆分时，总时间时Cn/4+Cn/4+Cn/4+Cn/4+=Cn，以此类推，总共拆分了log(n)次，所以快速排序最终的时间损耗为Cn×log(n)，也就是说快速排序的时间复杂度为O(nlog(n))。
   未完，待续...
上一篇：经典排序算法归纳笔记(2)
下一篇：经典排序算法归纳笔记(4)