希尔排序：
思想：
希尔排序是为了防止直接插入排序出现最坏情况所做的一种改进，将原本的排序过程分为预排序和直接插入排序两个阶段。
预排序阶段：将整个预排序的序列分为若干个待排序的子序列，分别进行插入排序，然后依次缩减分量；
直接插入排序阶段：待增量不断缩减后，序列基本达到有序状态，此时在进行一次直接插入排序。
图解示例（红色为有序序列黑色为无序序列）
代码实现：
#include<iostream> #include<assert.h> using namespace std; template<class T> void Print(const T* a, size_t n) { for (size_t i = 0; i < n; ++i) { cout << a[i] << " "; } cout << endl; } template<class T> struct Less //升序 { bool operator()(const T& l, const T& r) { return l < r; } }; template <class T> struct Great //降序 { bool operator()(const T& l, const T& r) { return l > r; } }; template<class T,class Compare> void ShellSort(T* a,size_t n) { assert(a); int gap = n; while (gap > 1) { gap = gap / 3 + 1; //+1是为了最后一次对全体数据进行插入排序 for (size_t i = gap; i < n; i++) { int end = i - gap; T tmp = a[i]; while (end >= 0) { if (Compare()(tmp, a[end])) { a[end + gap] = a[end]; end = end - gap; } else break; } a[end + gap] = tmp; } } } void TestShellSort() { int a[] = { 3, 5, 7, 2, 4, 1, 9, 8, 6 }; ShellSort<int, Less<int>>(a, sizeof(a) / sizeof(a[0])); Print(a, sizeof(a) / sizeof(a[0])); ShellSort<int, Great<int>>(a, sizeof(a) / sizeof(a[0])); Print(a, sizeof(a) / sizeof(a[0])); }
执行结果：
复杂度和稳定性：
时间复杂度：O(N)~O(N^2)
空间复杂度：O(1)
稳定性：不稳定
