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

C++ 希尔排序 个人笔记

希尔排序的由来:

8,9,1,7,2,3,5,4,6,0

上面的数组入如果用插入排序进行从大到小排列,需要移动的元素会很多,算法效率不高,于是希尔这人就提出了优化的插入排序。

希尔排序是希尔(Donald Shell)于1959 年提出的一种排序算法,希尔排序是一种插入排序的优化方案,是插入排序更高效的版本,也称为缩小增量排序,它与插入排序不同的是,它会优先比较距离较远的元素。

希尔排序是把记录按数组下标的一定增量分组，对每组进行插入排序，随着增量逐渐减少，每组包含的元素逐渐增多，当增量减少到1时，所有的元素被分为一组，实际上等同于执行一 次插入排序，算法便终止。

希尔排序的文字描述:

选择增量 ：gap=length/2，缩小增量：gap = gap/2 length代表数组的长度 gap 增量

希尔排序的代码实现

源代码

#include 
   
    using namespace std;void hillSort(int* arr, int len) {	//8,9,1,7,2,3,5,4,6,0  十个数	//增量为5 //每组数据的元素个数为2	int gap = len / 2; 	//增量不能为0或负数 gap = gap/2;依次减少增量,每组数据的元素个数逐渐增加	for (; gap > 0; gap = gap / 2) {		//从数组下标为5开始遍历到数组末尾		for (int i = gap; i < len; i++) {			int current = arr[i]; //记录当前下标中的数据			//preindex保存当前这组数据的前一个下标 若当前数组下标为5,			//那么在这一组数据的前一个下标就为0;			int preindex = i - gap;			//随着增量减少,每组数据的元素个数逐渐增加 			//preindex 数组下标不能为负数 且			//preindex下标中的数据 > 当前下标中的数据进入循环			while (preindex >= 0 && arr[preindex] > current) {				//为了让current可以插入有序数组到在preindex这个下标				//preindex 这个下标之后的下标中的数据平移(包括preindex 这个下标中的数据)				//preindex 这个下标的就可以被覆盖,不打乱当前的有序数组				arr[preindex + gap] = arr[preindex];				//preindex 这个下标依次递减到当前组的上一个下标				preindex = preindex - gap;			}			//因为经过preindex = preindex - gap所以要 + gap 才是current 要插入的位置			arr[preindex + gap] = current;		}	}}int main(void) {	int arr[] = { 8,9,1,7,2,3,5,4,6,0 };	int len = sizeof(arr) / sizeof(arr[0]);	hillSort(arr , len);	hillSort(arr , len);	for (int i = 0; i < len; i++) {		printf("%d\t", arr[i]);	}		return 0;}
   

测试结果

结尾

把上一节 插入排序没讲透的在这节代码的注释里做了一点补充

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