神刀安全网

《数据结构》排序——快速+归并(C++实现)


前言:《数据结构》作为计算机专业的一门重点学科,无论是将来考研、就业,对其的考察都是重中之重,之前的文章已经对此进行过论述。作为考察程序员“编程能力”的一种方式,考验的是我们如何将数据结构的思想用编程语言精确的编码出来。所有的《数据结构》课本都详细的讲解了每一种数据结构和算法的思想,然后给出具体的编程语言代码或者伪代码。算法思想只要认真看书,还是比较容易掌握的 ,真正考验我们的,是从算法思想到具体编码的这个思考过程,就是思考如何编码实现,这个过程是逃不掉的,除非参考别人的现有代码,但一段时间过后一定会忘记(百分之百的,我就忘记了无数次了)。所以,尽量在编程实现前,自己有个清晰的思路,尝试着自己去实现,然后调试,脑细胞不够用了再去参考别人写的。

0、代码:
本文全部代码放在 github:https://github.com/thinkChao/Data-Structure/blob/master/%E6%8E%92%E5%BA%8F(%E5%BF%AB%E9%80%9F%2B%E5%BD%92%E5%B9%B6).cpp 中,需要的可以下载或者直接复制代码运行,只有一个cpp文件,已经通过测试。

1、一点说明
之所以将这两个排序放在一起,是因为它们都使用了“分治策略”的思想,那既然都是分治,这两个算法的区别是什么呢?简单的说,快速是“从大到小”,归并是“从小到达”。具体来讲:快速是将一个数组根据一个数值先分成两边,左边的全部小于右边的,然后再对两边分别进行此操作,直到具体到每一个数;而归并是先两两合并,使得每两个是有序的,然后再两两合并,直到合成一个数组。

2、快速排序的三点说明
1)快速排序首先需要找个中间哨兵,用来进行分割。为了方便起见,选择将第一个值作为中间哨兵。

2)我们语言描述说“将大于哨兵值的放在其右,小于哨兵值的放在其左”,那编程怎么实现这个思想?这个就是考察一个人的编程能力,虽然这个实现起来还算比较简单。解决方案是:设置两个指针,一个从左往右,遇到比哨兵大或相等的就停止,然后另一个从右往左,遇到比哨兵小或相等的就停止,然后两个交换,接着继续,直到两个指针相遇的时候停止,注意这里有个坑。我们在描述思想的时候,一般不深入思考,通常是说在两个指针相遇的时候停止一次排序,可如果我们这样编程序“if(l_point==r_point)”,那就错了。因为只要我们在纸上画个图,自己移动指针走走看,会发现:除非正好这个值等于哨兵,否则两个指针是不可能重合相遇的,只会正好擦肩而过。所以条件应该是“if(l_point<r_point)”,这个地方要注意。

3)我们这里使用了递归,递归的特点是“好用不好想”,就是代码写起来很简短,但理解起来要有些困难,不过使用递归实现快速排序我个人觉得还挺好理解的,所以这里就使用了递归。不过归并排序并没有使用递归,因为我自己肯定实现不了,而且看别人的代码也不是特别理解,所以归并排序就没有使用递归。
一旦使用递归,就肯定会有一个终止条件的,就是指导程序在什么时候停止递归,否则岂不陷入了死循环,因此程序的最外围一定有个“if()语句”。所以我在写程序时,即使还没有清晰的思路,我仍是先把if()摆在那里,这个肯定错不了,然后就是思考括号里面的内容。这里插一句,对于我们的大部分算法程序,基本上都会用到“循环”,有循环就会有终止条件,一般也就是我们整个算法思想的终止条件了。因此,在写程序时,要好好想想算法终止的条件是什么,然后建立一个整体的框架,在这个框架里面填写内容。当然,大部分情况下,框架里面也会有循环,我们就以此类推吧,直到填充好整个程序。
对于快速排序,这里的算法终止条件是什么?大家可以想一想。答案:if(lf<rg)。

/*快速排序*/ void quick(int data[],int lf,int rg) {     int tmp;     //int mid=data[lf_idx];     int lf_idx=lf+1;     int rg_idx=rg;     if(lf<rg)     {         while(1)         {             for(int i=lf_idx;i<=rg;i++)          //一开始用的i<=rg_idx,这是不可以的             {                 if(data[i]>=data[lf])                 {                     lf_idx=i;                     break;                 }                 lf_idx=i;             }             for(int j=rg_idx;j>=lf;j--)             {                 if(data[j]<=data[lf])                 {                     rg_idx=j;                     break;                 }                 rg_idx=j;             }             if(lf_idx<rg_idx)             {                 tmp=data[lf_idx];                 data[lf_idx]=data[rg_idx];                 data[rg_idx]=tmp;             }             else                 break;         }         tmp=data[lf];         data[lf]=data[rg_idx];         data[rg_idx]=tmp;         quick(data,lf,rg_idx-1);         quick(data,rg_idx+1,rg);     } }

2、归并排序的三点说明
1)归并是两两归并,即相邻的两个序列进行归并。我们在描述时有种错觉就是,感觉所有的两两归并都是同时进行的,不知道大家有没有这种感觉。这就是一种模糊的感觉,这种感觉会给需要具体步骤的编程带来困扰,当然,只要我们意识到,然后理清思路就好了。
在这里,每一次的归并,都是从左往右,依次两两进行归并的。这里我们在单独进行两个序列的合并时要用到三个指针(left,mid,right),分别指向待合并两个序列的开端和结尾,那这不是需要四个吗?逻辑上是四个,但因为我们合并的是相邻序列,所以中间的那个可以顶俩,只需进行加一或减一操作即可。

2)前面我们提到,大部分算法都会涉及循环和其终止条件,归并也不例外。不过,归并的终止条件比快排的要稍微难想一点。但这是编程思路的重要一点,意识到要思考这一步,总比毫无头绪要强,所以我们要解决这个问题。那对于归并排序,什么时候终止呢?
直观的看,当合并到只有一个序列的时候,程序执行完成。那怎么用程序表示只有一个序列了呢?上一点我们说,用三个指针(left,mid,right),分别指向待合并两个序列的开端和结尾,这三个指针中,除了left的值从0开始,这个我们知道,而mid和right都是依据left来进行计算的,计算的方式是取一个值i,mid=f(i),right=f2(i),这样就算出了它们的值,这个其实是一个数学问题,不太容易想,可以通过找规律的方式解决。所以,我们这里就可以用i来作为我们的判断条件,至于什么条件我就不细讲了,都在程序中体现出来了,我只是想说说这个编程的大体思路,应该想哪些问题,至于解决问题,还是自己去想想吧,想不出来就看答案好了。

3)归并排序写了两个函数,其中merge()函数是专门用来进行两个序列合并的,所以单独写成一个函数,让程序思路看起来更清晰。

/*合并两个数组序列*/ void merge(int data[],int left,int mid,int right) {     int *temp_data = new int[right-left+1];     int i=left,j=mid+1;     int k=0;     while(i<=mid&&j<=right)     {         if(data[i]>data[j])         {             temp_data[k]=data[j];             k++;             j++;         }         else         {             temp_data[k]=data[i];             k++;             i++;         }     }     while(i<=mid)         temp_data[k++]=data[i++];     while(j<=right)         temp_data[k++]=data[j++];     for(i=left,j=0;i<=right;i++)                           data[i]=temp_data[j++]; }  /*归并排序*/ void merge_sort(int data[],int array_size) {     int left;     int right;     int mid;     for(int i=1;i<array_size;i=i*2)     {         left=0;         while(left<array_size)         {             mid=left+(i-1);             right=left+2*(i-1)+1;             if(mid>=array_size)                 mid=array_size-1;             if(right>=array_size)                 right=array_size-1;             merge(data,left,mid,right);             left=right+1;         }     } }

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » 《数据结构》排序——快速+归并(C++实现)

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址