难以想象的排序效率：希尔排序和插入排序的比较_千万数量希尔排序和插入排序 效率差多少?

            最开始学习排序是冒泡排序，那时候以为排序总不过就是两两比较，然后交换值而已：今天突然想实现一线以前所有学过的排序算法，对10w级别以上的数组进行排序的时候，希尔排序和插入排序的效率简直不在一个数量级上的。

           现在还有一个疑虑就是希尔排序的增量的确定的问题，我的方法是一个固定的增量区间，对排序的数组的元素个数 all = (int)log(size*4) + 1; //增量的个数是排序数数量级的ln，这样得到的增量数组

 对18W个数字排序，时间比较（毫秒） 希尔排序 0.1s 就完成了，有点不敢相信，插入排序用了4.2s

#include <iostream.h>
#include <windows.h>
#include <ctime>
#include <math.h>
#include <cstdlib>
 
void insertSort( int a[],int size);
 
//随机产生size个数组，存到pint里面
int randArr(int * pint , int size);
 
 
void ShellInsert(int a[],int size,int dk);
 
void ShellSort(int a[],int size,int dlta[],int t);
 
//得到增量值
int GenDis(int a[],int size);
 
void main()
{
 
	int  t =  0;
	int i =0,start=0,tsize=0;
		
	int dis[20] ={0};
 
 	tsize = 188880;
	cout<<"产生随机数"<<tsize<<"个"<<endl;
 
	t = GenDis(dis,tsize);
 
	cout<<"产生区间间隔距离"<<t<<"个：如下"<<endl;
	for( i = 0 ; i < t ; i++)
	{
		cout<<dis[i]<<" ";
	}cout<<"\n";
 
	int *pint=new int[tsize];
	
	int *pint2 =new int[tsize];
 
	if(! randArr(pint,tsize) )
		return;
 
	memcpy(pint2,pint,sizeof(int) * tsize);
 
 
	start  = GetTickCount();
	ShellSort(pint,tsize,dis,t );
	cout<<"time ShellSort used="<< GetTickCount() - start << endl;
 
	for( i = 0 ; i < t ; i++)
	{
		cout<<pint[i]<<" ";
	}cout<<"=========\n";
 
 
	/*插入排序的时间效率*/
	start  = GetTickCount();
 
	insertSort(pint2,tsize);
 
	cout<<"time insertSort used="<< GetTickCount() - start << endl;
 
	for( i = 0 ; i < t ; i++)
	{
		cout<<pint2[i]<<" ";
	}cout<<"=========\n";
 
 
	delete[] pint;
	delete[] pint2;
}
 
 
int GenDis(int a[],int size)
{
	int dlta []= {1500,1340,1160,1050,800,760,560,370,168,100,65,40,25,10,5,2,1};/*17个*/
 
	int all = (int)log(size*4) + 1;	//增量的个数是排序数组数量级的ln
 
	int  i = 0 , j = 0;
	
	if( all >= sizeof(dlta) /sizeof(dlta[0])) 
	{
		all = sizeof(dlta) /sizeof(dlta[0]);
		i = 0;
	}
	else
		i =  sizeof(dlta) /sizeof(dlta[0]) - all;
 
	for( j = 0 ; i < sizeof(dlta) /sizeof(dlta[0]) ; i++,j++)
	{
		a[j] =dlta[i];
	}
 
	return all;
}
 
void insertSort( int a[],int size)
{
	int i ,j;
	int pos;
	for( i = 1 ; i < size ; i++)
	{
		for(pos = a[i] ,j = i-1 ;  j >= 0 && a[j] > pos ; j--)
		{
			a[j+1] = a[j];
		}
		a[j+1] = pos;
	}
 
}
 
//产生size个随机数
int randArr(int * pint , int size)
{
	int i = 0;
	if(!pint)	return 0;
	srand((unsigned int)time(NULL));
 
	for( i = 0 ; i<size; i++)
	{
			pint[i] = rand() ;
 
			if( rand() % 10 == 1 && rand() % 10 == 1 && rand() % 10 == 1 &&pint[i] % 10 == 2)
				pint[i] *= -1;
	}
	return 1;
}
 
void ShellInsert(int a[],int size,int dk)
{
	int i= 0,j = 0 , pos;
	for(i = dk; i < size ; i++)
	{
		if(a[i] < a[i-dk])
		{
			pos = a[i];
			for( j = i -dk; j>=0 && pos < a[j] ;j -= dk)
			{
				a[j + dk] = a[j];
			}
			a[j+dk] = pos;
		}
	}
}
 
void ShellSort(int a[],int size,int dt[],int t)
{
	for(int k = 0; k <  t ; k++)
	{
		ShellInsert(a,size,dt[k]);
	}
}