希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL．Shell于1959年提出而得名。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。
image.png
希尔排序的时间复杂度的下界是O(n*log2n),与增量序列的选取有关 最差情况为O（n^2）
百度百科
计算步长之后间隔步长的两个数进行比较之后排序。
NSMutableArray *arrSort = [NSMutableArray arrayWithArray:@[@(7), @(3), @(15), @(5), @(11), @(2), @(4), @(9), @(6)]];
[self shellsort:arrSort];
/**
希尔排序
@param arrSort 数组
*/
- (void)shellsort:(NSMutableArray *)arrSort {
int i, j, gap, n;
n = (int)arrSort.count;
// 循环出步长
for (gap = n / 2; gap > 0; gap = gap / 2) {
for (i = gap; i < n; i++) {
for (j = i - gap; j >= 0; j = j - gap) {
if (arrSort[j] > arrSort[j + gap]) {
NSNumber *x = arrSort[j];
arrSort[j] = arrSort[j + gap];
arrSort[j + gap] = x;
}
}
}
}
}
image.png
