分治排序 算法導論 c++實作



    大二時就買了算法導論，偶爾也看了一些。但看的不是怎麼深入。現在該是補補算法的時候了，是以果斷啃啃書了。其中那個分治排序始終想不明白它的運作原理，不過在紙上畫了哈後大概明白了。其實有時候我們想不明白的東西可以通過模拟來幫助我們加深了解。

#include<stdio.h>

#include<iostream>

using namespace std;

void mege(int a[],int p,int q,int r)   //每次進行p到q和從q+1開始的q-p+1個的排序

{

 int n1=q-p+1;

 int n2=r-q;     right從q+1開始

 int *left=new int[n1+1];

 int *right=new int[n2+1];

 for(int i=0;i<n1;i++)

  left[i]=a[i+p];

 for(int j=0;j<n2;j++)

  right[j]=a[j+q+1];   //right從q+1開始

 left[n1]=5000;//最後一個放一個最大的哨兵

 right[n2]=5000;

 i=j=0;

 for(int k=p;k<=r;k++)

 {

  if(left[i]<=right[j])

  {

   a[k]=left[i];

   i=i+1;

  }

  else

  {

   a[k]=right[j];

   j=j+1;

  }

 }

}

void megsort(int a[],int p,int r)

{

 int q;

 if(p<r)    //遞歸到p=r時，不進入，可進行上一層的m（a，p，q，r）的排序，這時是兩兩排序(當然也會有一個元素的，之後再退出進行上一層的排序

 {     //每一次都是在上一次排序号的基礎上

  q=(p+r)/2;

  megsort(a,p,q);

  megsort(a,q+1,r);

  mege(a,p,q,r); 

 }

}

void main()

{

 int ssss[10]={2,55,3,545,2,56,77,5,0,6},i;

 cout<<"排序前:";

 for(i=0;i<10;i++)

  cout<<ssss[i]<<" ";

 cout<<endl;

 megsort(ssss,0,9);

 cout<<"排序後:";

 for(i=0;i<10;i++)

  cout<<ssss[i]<<" ";

 cout<<endl;

}