[SHL-SORT]Shell排序的实现，注意dist=(dist+1)/2 是不断变化的距离，初始时是(N+1)/2

vivion34

　　Shell排序的实现，注意dist=(dist+1)/2 是不断变化的距离，初始时是(N+1)/2，注意这个公式但dist为1时，dist之后永远为1.
　　/*******************************************************************
*
*    DESCRIPTION: Shell Sort [d[i+1]=(d+1)/2], d[0]=(count+1)/2
*                 d[] 为每趟的间距数组
*    AUTHOR: Neesky
*
*    DATE:2009-11-3
*
*******************************************************************/
/** include files **/
#include <iostream>
using namespace std;
int Array[10]={2,3,1,4,5,7,4,9,0,2};
/**
* Output Array
*
* @author NeeSky (2009-11-3)
*
* @param Array
* @param N
*/
void OutputArray(int Array[],int N)
{
cout<<&quot; &quot;;
for(int i=0;i<N;++i)cout<<Array<<&quot; &quot;;
cout<<endl;
return;
}
/**
* Shell Sort Functions
*
* @author NeeSky (2009-11-3)
*
* @param Arr
* @param N
*/
void ShellSort(int Arr[],int N)
{
if(N<=1)return;             /*more than 2 integer*/  
int dist=(N+1)/2;
while(dist>=1)              /*different  distance*/
{
int i=0;int j=i+dist;   /*mark*/
while(j<N)
{
while(i<j&&i+dist<N)
{
if(Arr>Arr[i+dist])std::swap(Arr,Arr[i+dist]);
++i;
}
j=j+dist;
}
cout<<&quot;dist-&quot;<<dist<<&quot; Shell Sort: &quot;;OutputArray(Arr,N);
if(dist==1)break;       /*Very Important*/
dist=(dist+1)/2;        /*when dist==1 dist==(dist+1)/2==1*/
}
return;
}
/**
* Just Fix the Shell Sorting Problem
*
* @author NeeSky (2009-11-3)
*
* @param Arr
* @param N
*/
void ShellSortFunction(int Arr[],int N)
{
cout<<&quot;/nBefor  Shell Sort: &quot;;OutputArray(Arr,N);
ShellSort(Arr,N);
cout<<&quot;After  Shell Sort: &quot;;OutputArray(Arr,N);
return;
}
/**
* The Main Programming
*
* @author NeeSky (2009-11-3)
*
* @param argc
* @param argv
*
* @return int
*/
int main (int argc, char *argv[])
{
int Array1[10]={2,3,1,4,5,7,4,9,0,2};
ShellSortFunction(Array1,10);
int Array2[10]={12,43,12,46,57,72,40,90,20,11};
ShellSortFunction(Array2,10);
return(0);
}

　　输出：

make -f &quot;Makefile&quot; CFG=Debug
mingw32-make: Nothing to be done for `all'.
Debug/ShellSort20091103.exe

Befor  Shell Sort:  2 3 1 4 5 7 4 9 0 2
dist-5 Shell Sort:  2 3 1 0 2 7 4 9 4 5
dist-3 Shell Sort:  0 2 1 2 3 4 4 9 7 5
dist-2 Shell Sort:  0 2 1 2 3 4 4 5 7 9
dist-1 Shell Sort:  0 1 2 2 3 4 4 5 7 9
After  Shell Sort:  0 1 2 2 3 4 4 5 7 9

Befor  Shell Sort:  12 43 12 46 57 72 40 90 20 11
dist-5 Shell Sort:  12 40 12 20 11 72 43 90 46 57
dist-3 Shell Sort:  12 11 12 20 40 46 43 90 72 57
dist-2 Shell Sort:  12 11 12 20 40 46 43 57 72 90
dist-1 Shell Sort:  11 12 12 20 40 43 46 57 72 90
After  Shell Sort:  11 12 12 20 40 43 46 57 72 90

版权声明：本文为博主原创文章，未经博主允许不得转载。