Archer, who doesn't know how to shoot...

首先我一定要提醒大家一件事情：謝爾排序法最一開始是用來改良「插入排序法」的，所以裡面的觀念不是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）