解析shell排序的實現代碼

代碼如下：

#include <iostream>
using namespace std;
void ShellQin(int A[],int n)
{
    int gap=n/2;
    int i,j;
    for(;gap>0;gap=gap/2)//設置初始gap，按照gap進行分組，gap按照gap/2遞減
    {
        //設置好gap以後，從gap開始一直到最後一個元素，為每一個元素在其對應的組進行插入排序。gap應該是該組所在位置的第2個元素，第一個元素位置是0
        for(i=gap;i<n;i++)
        {
            j=i;
            //對一組進行插入排序
            if(A[j-gap]>A[j])
            {
                /*如果A[j]>A[j-gap]意味著A[j]大於其所在組的前一個位置，那麼將
                  A[j]保存在temp中，將從組中所有大於A[j]的數後移，最後空出來的位置
                  存放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]的數
                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平方，認為希爾效率要比插排好的原因是，時間復雜度前面的系數要小於插排，特別是逆序的時候，很明顯的減少了比較的次數。就如同快排之於堆排，快排前的系數遠小於堆排，加上簡單易用所以稱為程序員們最愛。
下面的這種算法也叫做shell排序，與上面的區別在於進行插入排序的時候用交換相鄰兩個數據代替了移位（即先取出key關鍵字，將大於key的值向後移位）
代碼如下：

//交換兩個小數
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開始為所在的每個組進行插入排序，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;
                }
            }
        }
    }
}