## 希尔排序 1. 基本思想：希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。它与插入排序的不同之处在于，它会优先比较距离较远的元素。 ``` void shellSort(vector<int>& data) { int len = data.size(); int gap = len / 2; while (gap > 0) { for (int i = gap; i < len; ++i) { int tmp = data[i]; int prev = i - gap; while (prev >= 0 && data[prev + gap] < data[prev]) { data[prev + gap] = data[prev]; prev -= gap; } data[prev + gap] = tmp; } gap /= 2; } } ```