<学习笔记>归并排序与快速排序

2017-10-03

归并排序和快速排序的核心思想都是分治法。
由于本人并不是专于研究算法的，所以对于这两种算法的复杂度分析不进行研究与探讨。
这篇文章主要讨论这两种算法的原理理解与c++的描述。
归并排序：
假如给定序列21，25，49，25，16，8，31，41，
那么我们利用分治法的思想，大问题化成规模较小的相同的子问题，将序列进行划分，8个元素，好麻烦，那么我们就排4个吧？
最简单的情况呢，1个放在哪里，就是排好的咯。
21 25 49 25 16 08 31 41
21 25 49 25| 16 08 31 41 //划分过程；
21 25 | 49 25| 16 08 | 31 41
21 | 25 | 49 25| 16 | 08 | 31 | 41
21 25 | 25 49| 08 16 | 31 41
21 25 25 49| 08 16 31 41 //归并过程；
08 16 21 25 25 31 41 49
那么接下来就是我们要根据原理写出实现的代码了。

template<class T>
void merge(T list1[],T list2[],const int left,const int right,const int mid){
  for(int k=left;k<=right;k++){
    list2[k]=list1[k];    //list2是一个辅助数组，我们将list1的值拷贝到list2中，然后在归并到list1中；
  }
  int s1=left,s2=mid+1,t=left;  //s1，s2为list2的游标，t为list1的游标；list2分割为两个子表；
  while(s1<=mid&&s2<=right){
    if(list2[s1]<=list2[s2]) list1[t++]=list2[s1++];   //将两个子表的值进行比较，较小的放在新形成的母表的游标值较小的地方，也就是靠前放；
    else list1[t++]=list2[s2++];
  }
  while(s1<=mid) list1[t++]=list2[s1++];
  while(s2<=right) list[t++]=list2[s2++];//两个子表剩下的值再放入母表中；
}
template<class T>
void mergesort(T list[],T list2[],int left,int right){
  if(left>=right)return;
  int mid=(left+right)/2;
  mergesort(list,list2,left,mid);   //递归划分；
  mergesort(list,list2,mid+1,right);
  merge(list,list2,mid,right);  //合并；
}

所有的讲解都放在注释里了，思想很简单。
快速排序：
依然是上面的序列：21，25，49，25，16，8，31，41，
快速排序同样基于分治法。她的基本思想是任意取待排序列中的一个元素作为一个基准，依据这个基准的大小，将序列分为左右两个子序列，
左侧的都比她小，右侧的都比她大或者和她一样大。基准放在这两个子列中间就好了。重复上述方法，直到所有的元都待在它该待得位置
就好了。
[21 25 49 25 16 08 31 41] //(p)所指即为基准；
//p的个数相当于递归到子序列的深度；p->21;
[08 16] 21 [25 49 25 31 41]
//pp1->08,pp2->25;
08 [16] 21 25 [49 25 31 41]
//ppp1=16,ppp2=49;
08 16 21 25 [41 25 31] 49
//pppp=41;
08 16 21 25 [31 25] 41 49
//ppppp=31;
08 16 21 25 25* 31 41 49

放代码：

template<class T>
void quicksort(T list[], int a,int b){
  if(a<b){
    int i=partition(list,a,b);//划分；
    quicksort(list,a,i-1);//递归左子列排序；
    quicksort(list,i+1,b);//递归右子列排序；
  }
}
template<class T>
int partition(T list[],int p,int r){
  int i=p;             //向右走的一个游标；
  int j=r+1;           //向左走的一个游标；
  T x=list[p];         //基准；
  while(true){
    while(list[++i]<x&&i<r);  //自左向右找寻第一个比基准大的位置；
    while(list[--j]>x);       //自右向左找寻第一个比基准小的位置；
    if(i>=j)break;            //边界；
    int temp=list[i];         //找到了就交换位置呗；
    list[i]=list[j];
    list[j]=temp;
  }
  list[p]=list[j];     //将基准与所找到的满足上述目标特性的最后一个元进行位置交换；
  list[j]=x;           
  return j;            //返回此时的母串的基准的位置，为了进行子序列的递归排序；
}

这就是我对这两种基于分治法的排序方法的理解，如有错误，那一定是个意外哦。