本文共 951 字，大约阅读时间需要 3 分钟。

希尔排序（改进的插入排序）：

希尔排序属于插入类排序,是将整个有序序列分割成若干小的子序列分别进行。

排序过程：先取一个正整数d1<n，把所有序号相隔d1的元素放一组，组内进行；然后取d2<d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止。

但是： 希尔排序会改变相同元素的原先相对位置， 也就是说希尔排序是不稳定的。

实现：

d 选取好坏会影响排序的效果 这里是d/2(并非好的选择)

void shell_sort(int a[], int n)	{		int i, j, d;		int tmp;		for(d = n/2; d > 0; d /= 2){ //最后 d 为 1 			for(i = d; i < n; i++ ){//从d开始往后依此排 与当前元素相差d整数倍距离的元素				tmp = a[i];				for(j = i; j >= d && a[j-d] > tmp; j -= d){					a[j] = a[j-d];				}				a[j] = tmp;			}		}	}

改进的希尔排序:(使用Sedgewick增量序列)

void shell_sort(int a[], int n)	{		int i, j, d;		int tmp;		int Si;		int Sedgewick[] = {929, 505, 209, 109, 41, 19, 5, 1, 0}; 		for(Si = 0;  Sedgewick[Si] >= n; Si++ )//最大增量需要小于数组大小		for(d = Sedgewick[Si]; d > 0; d = Sedgewick[++Si]){ //最后 d 为 1 			for(i = d; i < n; i++ ){				tmp = a[i];				for(j = i; j >= d && a[j-d] > tmp; j -= d){					a[j] = a[j-d];				}				a[j] = tmp;			}		}	}

转载地址：http://xximi.baihongyu.com/