- 简介
希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
- 基本思想
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt = 1(dt<dt-1...d2,d1)，即所有记录放在同一组中进行直接插入排序为止。
算法先将要排序的一组数按某个增量d分成若干组，每组中记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成一组，排序完成。一般的初次取序列的一半为增量，以后每次减半，直到增量为1。
如：一组数据95, 45, 15, 78, 84
增量为2时，分成如下两组子序列：
95 __ 15 __ 84
__ 45 __ 78 __
对这两组子序列做直接插入排序后得：
15 45 84 78 95
然后取增量为1，得到下面一组子序列：
15 45 84 78 95
对这组子序列做直接插入排序得：
15 45 78 84 95
- C语言实现
void shellSort(int num[],int count) {
int shellNumber = 2;//每次取序列总数的一半，
int d = round(count / shellNumber);//增量
while (d > 0) {
for (int i = d; i < count; i++) {
int temp = num[i];
int j = i;
while (j >= d && num[j - d] > temp) {
num[j] = num[j - d];
j = j - d;
}
num[j] = temp;
}
d = round(d / shellNumber);
}
}
//调用
int number[5] = {95, 45, 15, 78, 84};
shellSort(number, 5);
for (i = 0; i < 5; i++) {
printf("%d\n", number[i]);
}
- OC实现
- (void)shellSortWithNumbers:(NSMutableArray *)numbers {
int shellNumber = 2;
int d = round(numbers.count / shellNumber);
while (d > 0) {
for (int i = d; i < numbers.count; i++) {
int temp = [numbers[i] intValue];
int j = i;
while (j >= d && [numbers[j - d] intValue] > temp) {
numbers[j] = numbers[j - d];
j = j - d;
}
numbers[j] = @(temp);
}
d = round(d / shellNumber);
}
NSLog(@"%@",numbers);
}
//调用
NSMutableArray *array = [NSMutableArray arrayWithObjects:@(10),@(4),@(8),@(99),@(16),@(19),@(3), nil];
[self shellSortWithNumbers:array];
- 时间复杂度
最好情况的时间复杂度O(n)。
最坏情况的时间复杂度O(n^2)
平均时间复杂度O(n^1.3)
- 算法稳定性
由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。
