Shell排序使用一個遞增序列h1,h2,h3...hk. h1==1。
從hk開始，每次將間隔hx的序列排好序，直到h1。間隔hx的序列排好序的數(shù)組可以稱之為hx有序。
Shell排序有一個重要的性質(zhì)是一個hx有序數(shù)組，必然是一個hx+1有序數(shù)組。
每一遍排序過程可以使用插入排序。
Shell排序的性能取決于遞增序列的選擇。下面代碼的遞增序列是len/2,len/4...,1.
int?shell_sort(int?*array,int?begin,int?end)
{
????if(array==NULL||begin>end)?return?0;
????int?len?=?end-begin+1;
????int?i,j,gap,tmp;
????for(gap=len/2;gap>=1;gap/=2){
???????for(i=begin+gap;i<=end;++i){
???????????j?=?i;
???????????tmp?=?array[j];
???????????while(?j-gap>=begin&&array[j-gap]>tmp?){
???????????????array[j]?=?array[j-gap];
???????????????j-=gap;
???????????}
???????????array[j]?=?tmp;
???????}
????}
????return?1;
}