快捷導(dǎo)航

解析shell排序的實現(xiàn)代碼

更新時間：2013年05月16日 17:27:42 作者：

本篇文章是對shell排序的實現(xiàn)代碼進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下

#include <iostream> 
using namespace std; 
void ShellQin(int A[],int n) 
{ 
    int gap=n/2; 
    int i,j; 
    for(;gap>0;gap=gap/2)//設(shè)置初始gap，按照gap進(jìn)行分組，gap按照gap/2遞減 
    { 
        //設(shè)置好gap以后，從gap開始一直到最后一個元素，為每一個元素在其對應(yīng)的組進(jìn)行插入排序。gap應(yīng)該是該組所在位置的第2個元素，第一個元素位置是0 
        for(i=gap;i<n;i++) 
        { 
            j=i; 
            //對一組進(jìn)行插入排序 
            if(A[j-gap]>A[j]) 
            { 
                /*如果A[j]>A[j-gap]意味著A[j]大于其所在組的前一個位置，那么將 
                  A[j]保存在temp中，將從組中所有大于A[j]的數(shù)后移，最后空出來的位置 
                  存放A[j] 
                */
                int temp=A[j];//保存A[J] 
                do
                { 
                    A[j]=A[j-gap]; 
                    j=j-gap; 
                }while(j>=0&&temp<A[j]);//后移每一個大于A[j]的數(shù) 
                A[j+gap]=temp;//將A[j]插入到合適的位置 
            } 
        } 
    } 
    for(i=0;i<n;i++) 
    { 
        cout<<*(A+i)<<" "; 
    } 
} 
int main1() 
{ 
    int a[]= {5,4,3,21,1,100,93,1,3,2,4}; 
    ShellQin(a,11); 
    return 0; 
}

和朋友討論過后，雖然希爾和插排最壞的情況都是n平方，認(rèn)為希爾效率要比插排好的原因是，時間復(fù)雜度前面的系數(shù)要小于插排，特別是逆序的時候，很明顯的減少了比較的次數(shù)。就如同快排之于堆排，快排前的系數(shù)遠(yuǎn)小于堆排，加上簡單易用所以稱為程序員們最愛。
下面的這種算法也叫做shell排序，與上面的區(qū)別在于進(jìn)行插入排序的時候用交換相鄰兩個數(shù)據(jù)代替了移位（即先取出key關(guān)鍵字，將大于key的值向后移位）

復(fù)制代碼代碼如下:

//交換兩個小數(shù) 
void swapdouble(double *a,double *b){ 
   double temp=*a; 
   *a=*b; 
   *b=temp; 
} 
void Shell(double* p,int n) 
{ 
    int gap=n/2; 
    int i,j; 
    for(;gap>0;gap=gap/2) 
    { 
        for(i=gap;i<=n-1;i++)//從gap開始為所在的每個組進(jìn)行插入排序，i=gap是該組的第二個元素 
        { 
            j=i; 
            if(*(p+j)<*(p+j-gap)) 
            { 
                while(j>=gap && *(p+j)<*(p+j-gap)) 
                { 
                    swapdouble(p+j,p+j-gap); 
                    j=j-gap; 
                } 
            } 
        } 
    } 
}