---

前言

编程语言：C++
编译器：vs2022

---

一、希尔排序思想

插入排序适合用在数列已经基本有序了，当我们在处理一些大规模无序的数值时，插入排序就显得比较拉跨，所以我们可以，先将序列变成基本有序，最终再利用插入排序进行排序这样是不是会更好。所以也就有了希尔排序这个算法，希尔排序通过创建增量来实现对序列的跳跃式交换，再通过一定比例减少增量再次跳跃式交换最终当增量为1时就是插入排序。这样也就实现了希尔排序

二、希尔排序

#define MAXSIZE 10
#include <iostream>
using namespace std;//希尔排序
int main()
{int i, j,h;int arr[MAXSIZE + 1] = { 0,6,4,2,8,9,5,11,10,3,7 };//创建数组数据arr[0]为哨兵h = MAXSIZE;//将要排序的长度给增量hdo{h = h / 3 + 1;for (i = h+1; i <= MAXSIZE; i++){if (arr[i - h] > arr[i])//比较是否需要发生移动{arr[0] = arr[i];//将要插入的值赋值给哨兵for (j = i - h; j > 0 && arr[j] >= arr[0]; j -= h)arr[j + h] = arr[j];//向后移动arr[j + h] = arr[0];//插入正确位置}}} while (h > 1);for (i = 1; i <= MAXSIZE; i++)cout << arr[i] << " ";system("pause");return 0;
}

总结

希尔排序是插入排序的一种改进，使得希尔排序能够再大规模无序的条件下也能够充分发挥作用。希尔排序时间复杂度：O(nlogn)~O(n²)