算法思想

希尔排序又叫作缩小增量排序，其本质还是插入排序，只不过是将待排序列按某种规则分成几个子序列，分别对这几个子序列进行直接插入排序。这个规则的体现就是增量的选取，如果增量为1, 就是直接插入排序。例如，先以增量5来分割序列，即将下标为0、5、10、15... 的关键字分成一组，将下标为1、6、11、16...的关键字分成另一组等，然后分别对这些组进行直接插入排序，这就是一趟希尔排序。将上面排好序的整个序列，再以增量2分割，即将下标为0、2、4、6、8... 的关键字分成一组，将下标为1、3、5、7、9...的关键字分成另一组等，然后分别对这些组进行直接插入排序，这又完成了一趟希尔排序。最后以增量1分割整个序列，其实就是对整个序列进行一趟直接插入排序，从而完成整个希尔排序。

执行流程

代码

该算法的核心代码：

/* 希尔排序 */
/* a[]指的是要进行排序的数组；n指的是a数组的长度；dt[]指的是增量数组；t指的是dt数组的长度 */ 
void shellSort(int a[],int n,int dt[],int t){
	for(int i=0;i<t;i++){// 遍历增量数组中的增量 
		int gap=dt[i];// 增量的值5,3,1 
		for(int k=gap; k<10; k++) {
			int temp=a[k];//将要插入的数放入t中
			int j=k-gap;
			while(j>=0&&temp<a[j]) {//t若比前面位置上的数字小，前面数就要后移
				a[j+gap]=a[j];//后移
				j=j-gap;//找到前面一个位置上的数，反正这步我推了好久
			}
			a[j+gap]=temp;//t插入这个位置
		}
	}
}

完整代码：

#include<stdio.h>

/* 打印数组元素 */
void print(int nums[],int n) {
	printf("\n");
	for(int i=0; i<n; i++) {
		printf("%d\t",nums[i]);
	}
	printf("\n");
}

/* 希尔排序 */
/* a[]指的是要进行排序的数组；n指的是a数组的长度；dt[]指的是增量数组；t指的是dt数组的长度 */ 
void shellSort(int a[],int n,int dt[],int t){
	for(int i=0;i<t;i++){// 遍历增量数组中的增量 
		int gap=dt[i];// 增量的值5,3,1 
		for(int k=gap; k<10; k++) {
			int temp=a[k];//将要插入的数放入t中
			int j=k-gap;
			while(j>=0&&temp<a[j]) {//t若比前面位置上的数字小，前面数就要后移
				a[j+gap]=a[j];//后移
				j=j-gap;//找到前面一个位置上的数
			}
			a[j+gap]=temp;//t插入这个位置
		}
	}
}

int main() {
	int nums[]= {49,38,65,97,76,13,27,49,55,4};
	int n=10;// nums数组的长度 
	printf("排序前：");
	print(nums,n);

	int dt[]={5,3,1};// 增量数组
	int t=3;// dt数组的长度 
	shellSort(nums,n,dt,t);// 进行希尔排序
	printf("排序后：");
	print(nums,10);

	return 0;
}

运行结果如下：