|
|
???今天復習另外兩種排序算法：Shell排序＆歸并排序。 ??? ???Shell排序是插入排序的一種。昨天已經復習了兩種插入排序算法——直接插入排序＆折半插入排序，Shell排序屬于的三種插入排序算法。 ??? ???Shell排序的基本思路是將記錄按照一定的間隔進行插入式排序，然后逐漸縮小間隔到1。當間隔縮小到1時，Shell排序相當于直接插入排序。但是因為前面的排序過程基本上已經定下了記錄的大概位置，所以并不需要比較和移動很多記錄。因此算法的效率要比直接插入排序好。 ??? ???Shell排序：
 void?ShellSort(RcdType?r[],int?n)
   {
 ????int?i,j,d;
????d=n/2;
  ????while(d>0){
????????for(i=1+d;i<=n;i++){
????????????r[0]=r[i];
????????????j=i-d;
????????????while(j>0?&&?r[j].key>r[0].key){
????????????????r[j+d]=r[j];
????????????????j-=d;
 ????????????}
????????????r[j+d]=r[0];
????????}
????????d/=2;
????}
 }???今天復習的另外一種排序算法是歸并排序。歸并排序的基本思想是將兩個有序記錄集歸并為一個有序的記錄集。具體實現起來有兩種方法，即所謂的自頂向下法和自底向上法。我個人認為自頂向下法更為簡單。 ??? ???自頂向下的歸并排序(運用遞歸)：
void?Merge(RcdType?r[],int?l,int?m,int?h)
{
????int?i,j,k,*r2;
????i=l;
????j=m+1;
????k=0;
????r2=(int?*)?malloc(sizeof(int)*(h-l+1));
????while(i<=m?&&?j<==h){
????????if(r[i].key<r[j].key)?r2[k++]=r[i++];
????????else?r2[k++]=r[j++];
????}
????while(i<=m)?r2[k++]=r[i++];
????while(j<=h)?r2[k++]=r[j++];
????for(k=0,i=l;i<=h;)
????????r[i++]=r2[k++];
????free(r2);
}
void?MergeSort(RcdType?r[],int?s,int?e)
{
????int?m;
????if(s!=e){
????????m=(s+e)/2;
????????MergeSort(r,s,m);
????????MergeSort(r,m+1,e);
????????Merge(r,s,m,e);
????}
} ???自底向上的歸并排序：
void?Merge(RcdType?r[],int?l,int?m,int?h)
{
????int?i,j,k,*r2;
????i=l;
????j=m+1;
????k=0;
????r2=(int?*)?malloc(sizeof(int)*(h-l+1));
????while(i<=m?&&?j<==h){
????????if(r[i].key<r[j].key)?r2[k++]=r[i++];
????????else?r2[k++]=r[j++];
????}
????while(i<=m)?r2[k++]=r[i++];
????while(j<=h)?r2[k++]=r[j++];
????for(k=0,i=l;i<=h;)
????????r[i++]=r2[k++];
????free(r2);
}
void?MergePass(RcdType?r[],int?length,int?n)
{
????int?i;
????for(i=1;i+length*2-1<=n;i=i+length*2){
????????Merge(r,i,i+length-1,i+2*length-1);
????}
????if(i+length-1<n)?Merge(r,i,i+length-1,n);
}
void?MergeSort(RcdType?r[],int?n)
{
????int?length;
????for(length=1;length<n;length*=2){
????????MergePass(r,length,n);
????}
}
|