排序算法——希尔排序

 66		43		89		98		12		18		15		23		33		50
a[0]   a[1]    a[2]    a[3]    a[4]    a[5]    a[6]    a[7]    a[8]    a[9]		
//①初始步长为len/2也就是[10/2]=5，则
a[0]a[5]一组 a[1]a[6]一组 a[2]a[7]一组 a[3]a[8]一组 a[4]a[9]一组，共5组
//首先在5组内分别进行插入排序，变为
 18		15		23		33		12		66		43		89		98		50
a[0]   a[1]    a[2]    a[3]    a[4]    a[5]    a[6]    a[7]    a[8]    a[9]	
//这轮排序，元素位置变化次数为8次
//②进行第一轮排序后，步长变为len/4向下取整也就是[10/4]=2，则
a[0]a[2]a[4]a[6]a[8]一组 a[1]a[3]a[5]a[7]a[9]一组，共2组
//在2组内分别进行插入排序，变为
 12		15		18		33		23		50		43		66		98		89
a[0]   a[1]    a[2]    a[3]    a[4]    a[5]    a[6]    a[7]    a[8]    a[9]		0
//这轮排序，元素位置变化次数为6次
//③排序后，步长继续变化，变为len/8向下取整也就是[10/8]=1，此时就是插入排序，变为
 12		15		18		33		23		50		43		66		98		89
a[0]   a[1]    a[2]    a[3]    a[4]    a[5]    a[6]    a[7]    a[8]    a[9]		1
 12		15		18		33		23		50		43		66		98		89
a[0]   a[1]    a[2]    a[3]    a[4]    a[5]    a[6]    a[7]    a[8]    a[9]		2
 12		15		18		33		23		50		43		66		98		89
a[0]   a[1]    a[2]    a[3]    a[4]    a[5]    a[6]    a[7]    a[8]    a[9]		3
 12		15		18		23		33		50		43		66		98		89
a[0]   a[1]    a[2]    a[3]    a[4]    a[5]    a[6]    a[7]    a[8]    a[9]		4
 12		15		18		23		33		50		43		66		98		89
a[0]   a[1]    a[2]    a[3]    a[4]    a[5]    a[6]    a[7]    a[8]    a[9]		5
 12		15		18		23		33		43		50		66		98		89
a[0]   a[1]    a[2]    a[3]    a[4]    a[5]    a[6]    a[7]    a[8]    a[9]		6
 12		15		18		23		33		43		50		66		98		89
a[0]   a[1]    a[2]    a[3]    a[4]    a[5]    a[6]    a[7]    a[8]    a[9]		7
 12		15		18		23		33		43		50		66		98		89
a[0]   a[1]    a[2]    a[3]    a[4]    a[5]    a[6]    a[7]    a[8]    a[9]		8
 12		15		18		23		33		43		50		66		89		98
a[0]   a[1]    a[2]    a[3]    a[4]    a[5]    a[6]    a[7]    a[8]    a[9]		9
//此轮排序中，元素位置变化只有第4、6、9次各变化了2个元素的位置，元素位置变化共有6次

//①②③轮结束后，元素位置变化次数总共有8+6+6=20次，相比较插入排序32次元素位置变化次数节省了32-20=12次，12/32=3/8=0.375=37.5%，优化了大概37.5%的元素位置变化次数

代码：
//希尔排序
void shell_sort(int* a, int len){
	int step = len / 2;

	int temp;
	int j;
	while (step){//根据步长来分组
		//组内作插入排序

		for (int i = step; i < len; i++){//从step开始  len-1-step轮
			temp = a[i];//临时保存待插数据

			for (j = i - step; j >= 0; j -= step){//待插数据前一个开始往前循环（越界循环结束）
				if (a[j]>temp){//比待插数据大则往后覆盖
					a[j + step] = a[j];
				}
				else{
					break;
				}
			}
			//用待插数据覆盖回来（第二步结束后下标的下一个位置）
			a[j + step] = temp;
		}
		step >>= 1;//step = step / 2;
	}
}