Chinaunix首页 | 论坛 | 博客
  • 博客访问: 4214425
  • 博文数量: 82
  • 博客积分: 671
  • 博客等级: 上尉
  • 技术积分: 24576
  • 用 户 组: 普通用户
  • 注册时间: 2010-12-18 16:08
个人简介

www.kernel.org

文章分类

全部博文(82)

文章存档

2016年(1)

2015年(3)

2014年(12)

2013年(14)

2012年(52)

分类: C/C++

2014-04-30 13:41:03

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

归并排序
   归并排序是基于归并操作的,归并操作的思想很简单,针对两个已经排好序的有序序列:
   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.         }

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

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

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

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

点击(此处)折叠或打开

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

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

  10.     //归并的过程
  11.     return merge_ops(a,len/2,a+len/2,len-len/2);
  12. }
    归并排序的效率还是蛮高的,它包含了“拆分”和“归并”两个过程。对于长度为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. }

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

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

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

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

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

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

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

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

点击(此处)折叠或打开

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

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

   堆排序的时间主要包含两部分:“建堆的时间”+“排序时调整堆的之间”。建堆和调整堆时我们都调用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];          //找到后执行一次赋值,然后开始从前向后找

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

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

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

点击(此处)折叠或打开

  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))。
   未完,待续...

阅读(6984) | 评论(0) | 转发(11) |
给主人留下些什么吧!~~