[C++知识库]希尔排序 c/c++描述

??希尔插入排序，是对直接插入排序的改进。当数组很大，或者顺序很乱时候，由于比较和移动元素的次数太多，直接插入排序的效率会下降。对之的改进就是，分组排序，即希尔排序。
??希尔排序，是把数组分组，每个子数组跨度很大，其中元素位置分散，总元素数较少。先对子数组排序，由于数目少，所以效率高，实现分组有序。当不再分组时，由于整体基本有序，元素移动次数少，直接插入排序，仍然有高的效率。希尔排序使时间复杂度减到了O（n ^2）以下。
??这些链接讲解的都很好。
【数据结构与算法】高级排序（希尔排序、归并排序、快速排序）完整思路，并用代码封装排序函数_零一的博客-CSDN博客
https://blog.csdn.net/l_ppp/article/details/108855298
??
??https://www.bilibili.com/video/BV1ez4y1Z7Ch B站懒猫老师
以下是完整代码，测试结果试过了，是对的。

#include<iostream>
using namespace std;

void shellInsertSort(int array[],int length) {
	int temp;
	int gap = length / 2;
	int indexI,indexJ;
	
	while (gap > 0) {
		for (indexI = gap; indexI < length; indexI++) {
			temp = array[indexI];
			indexJ = indexI - gap;

			while (indexJ >= 0 && temp < array[indexJ]) {
				array[indexJ + gap] = array[indexJ];
				indexJ -= gap;
			}
			
			array[indexJ + gap] = temp;
		}

		gap = gap / 2;
	}

	for (int i = 0; i < length; i++)
		cout << array[i] << ' ';
}

int main() {
	int array[] = {1,0,9,6,4,5,8,7,3,2}, length = 10;
	shellInsertSort(array,length);
	return 0;
}