前言： 数据序列1： 13-17-20-42-28 利用插入排序，13-17-20-28-42. Number of swap:1; 数据序列2： 13-17-20-42-14 利用插入排序，13-14-17-20-42. Number of swap:3; 如果数据序列基本有序，使用插入排序会更加高效。
基本思想： 在要排序的一组数中，根据某一增量分为若干子序列，并对子序列分别进行插入排序。 然后逐渐将增量减小,并重复上述过程。直至增量为1,此时数据序列基本有序,最后进行插入排序。
#include<iostream> #include<vector> using namespace std; void print(vector<int> a) { for (int i = 0; i < a.size(); i++) { cout << a[i] << " "; } cout << endl; } int main() { vector<int> arr{0,9,1,5,8,3,7,4,6,2}; cout << "原数组:" << endl; print(arr); //希尔排序 //在这之前排序算法基本是O(n2)，希尔排序是突破这个算法的第一批算法之一 int temp ; int increment = arr.size(); while (increment>1) { increment = increment / 3 + 1;//分割为若干个子序列,increment是增量 cout << "increment " << increment << endl; for (int i = increment; i < arr.size(); i++) { if (arr[i] < arr[i - increment]) { temp = arr[i]; int j; for (j = i - increment; j > 0 && arr[j] > temp; j -= increment) {//此处for循环是插入排序的for循环 arr[j+increment] = arr[j];//记录后移 } arr[j+increment] = temp;//插入排序一样 print(arr); } } } cout << "排序后：" << endl; print(arr); system("pause"); }时间复杂度分析：希尔排序不是随便分组后的各自排序，而是相隔某个增量的记录组成一个子序列，实现跳跃式的移动，使得排序的效率增高。在这里：增量的选择是一个关键，目前还是一个难题，不过大量的研究表明，当增量序列为时，可以取得不错的效果。其时间复杂度为，要好于直接排序的O（n2），增量序列的最后一个增量必须是1才行。另外由于记录是跳跃式的移动，希尔排序不是一个稳定的排序算法。
不管怎么说：shell排序使我们突破了慢速排序的时代（超越了n方的时间复杂度）。之后更为高效的排序算法也出现了
