希尔排序算法-OC实现

• 简介

希尔排序(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排序是不稳定的。