首先我一定要提醒大家一件事情：谢尔排序法最一开始是用来改良「插入排序法」的，所以里面的观念不是SWAP，而是「插入」。会这样写一个前提的原因，是因为我在上课的时候，某个老师将「插入」这个动作误植为「交换」，所以让很多人一头雾水。说真的，不是我偏，但身为一个补习班老师，你就不能讲得正确一点吗！？Doth thou monther know you were such idot? (#注1）

谢尔贝壳排序法要先找到级距（gap），最简单的级距就是把阵列大小/2。相同级距的值作为一个位元组进行插入排序，结束之后级距/2进入回圈，直到级距等于1 为止。

 

#include <iostream>
#include <time.h>
#include <stdlib.h>
using namespace std;
#define SWAP(a,b){ int temp =a;a=b;b=temp;}

const int size = 10;

void print(int a[],int size)
{
    for (int i=0;i<size;i++)
    {
        cout<<a[i]<<"\t";
    }
    cout<<"\n";
}

void IS(int a[],int size)//这边是插入排序法，写在一起可以比对一下差别
{
    for (int i=1; i<size;i = i+1)
    {
        int t=a[i];
        int j=i-1;
        while(t<a[j] )              //当 [x] 的值比较大的时候
        {                                //把 [x-1] 放进 [x] 里
            a[j+1]=a[j];           //终止状况1. 触底||2. 遇到比 [x] 更小的值
            j=j-1;                    //最后把事先拿出来存著的 [x] 值放回去
            if(j==-1){ break;}//其实这一段我觉得用SWAP会更简单，所以我下面就直接用SWAP了ㄎㄎㄎ
        }
        a[j+1]=t;
    }
}

void SHELL(int a[],int size)//贝壳排序
{
int gap = size / 2; //找到级距

while(gap > 0)//级距会不断地除以二直到log以二为底的gap为零
{

    for(int i=0;i<gap;i+=1)//从位置0到gap的前一个位置
    {
        for(int j=i+gap;j<size;j+=gap)//从gap位置开始，结束于超出原本array大小为止
        {
            for(int k=j-gap;k>=i;k-=gap)//从gap的前一个级距位置开始，直到触底（底为 i ）
            {
                if(a[k]>a[j]){ SWAP(a[k],a[j]);}//有比较大的就交换，一看到比较小或者相等的就跳出
                else break;                               //基本上算是插入与交换的应用... 比较好理解，效能差不多
            }
        }
      }
      gap /= 2;
    }
}

void main ()
{
    int a[size]={0};
    srand(time(NULL));
    for (int i=0;i<size;i++)
    {
        a[i]=rand()%(100)+1;
    }
    print(a,size);
//  IS(a,size);
    SHELL(a,size);
    print(a,size);

 

    system("pause");
}

 

注1: 这梗来自于2012年超级爽片复仇者联盟中，东尼屎塔嗑初遇索尔（应该是索尔吧XD）的时候酸他的话：Doth thou mother knoweth you weareth her drapes？（莎士比亚腔，意指：真没想到你长这么大了还在玩超人游戏...。不过这句话其实屎塔嗑是没有资格说的，因为在场三个人里面最幼稚就他XDDDD）