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