排序 --- 希尔排序

1. 名字由来

希尔排序,也称递减增量排序算法 。 是 D.L.Shell 于1959年提出来的一种排序算法，在这之前排序算法的时间复杂度基本都是O（n²）,希尔排序算法是突破这个时间复杂度的第一批算法之一。

2. 起因

直接插入排序在特定条件下的效率是非常高的
1.记录本身是基本有序的，只需少量的插入操作，就可以完成整个记录集的排序工作
2.记录数比较少
要满足这两个条件比较难，希尔排序就是去创造这两个条件，所以说希尔排序是插入排序的改进版本。

3. 基本思想

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。 

4. 如何分组

比如现在有序记录是{9,1,5,8,3,7,4,6,2}，现在将它分成三组{9,1,5},{8,3,7},{4,6,2} 排序后变成{1,5,9},{3,7,8},{2,4,6}再合并他们成{1,5,9,3,7,8,2,4,6}，此时这个序列还是杂乱无序，谈不上基本有序，因为所谓的基本有序，就是小的关键字基本在前面，大的基本在后面，像{2,1,3,6,4,7,5,8,9}这样的称为基本有序，但是{1,5,9,3,7,8,2,4,6}这样的9在第三位，2 在倒数第三位就谈不上基本有序

我们分隔待排序记录的目的是减少待排序记录的个数，使整个序列向基本有序发展，但是像上面这样的分隔达不到要求。因此，采取跳跃分隔的策略：将相距某个"增量"的记录组成一个子序列，这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序。

5. 算法实现

#pragma mark - c语言版本
- (void)k_c_shellSort {
    int a[] = {9,1,5,8,3,7,6,0,2,4,1};
    int arrayLength = sizeof(a)/sizeof(int);
    int increment =  arrayLength / 2; 
    while (increment >= 1) {
        for (int i = increment; i < arrayLength; i++) {
            int temp = a[i];
            for (int j = i ; j >= increment && temp < a[j-increment]; j-=increment) {
                a[j] = a[j-increment];
                a[j-increment] = temp;
            }
        }
        increment = increment /2;
    }
    
    for(int i = 0 ;i < arrayLength; i++)
    {
        printf("%d ",a[i]);
    }
}

 #pragma mark - OC
-(void)shellSort:(NSMutableArray *)list {
    int increment = (int)list.count/2;
    while(increment >=1) {
        NSLog(@"当前increment为：%d",increment);
        
        for(int i = increment ; i < list.count; i++){
            NSString *temp = list[i];
            int j = i;
            
            NSLog(@"比较的的两个数是 %@ --- %@",temp,list[j-increment]);
            for ( ; j >= increment && [temp integerValue] < [list[j-increment] intValue]; j-=increment) {
                
                list[j] = list[j-increment];
                list[j-increment] = temp;
                 NSLog(@"+++++++++++ 交换的两个数是 %@ --- %@",temp,list[j]);
            }
        }
        increment = increment /2;
}}


 #pragma mark - 使用
    NSArray *arr = @[@"9",@"1",@"5",@"8",@"3",@"7",@"6",@"0",@"2",@"4",@"1"];
    NSMutableArray *arr1 = [NSMutableArray arrayWithArray:arr];
    [self shellSort:arr1];

   NSLog(@"arr1:%@",arr1);
   arr1:(0,1,1,2,3,4, 5,6,7,8,9)

sheel1.png

一.   11/2 =5, 当增量为5的时候 将记录归并成子数组
{9,7,1}  {1,6} {5,0} {8,2} {3,4}   //这个数组是虚拟数组,只是用来将需要比较的数据分类一下，便于理解
第一次插入排序后变为：7,1,0,2,3,9,6,5,8,4,1
此时虚拟数组变为 {7,9,1}{1,6},{0,5} {2,8} {3,4}

需要接着将第一个虚拟数组排序
此时最后一位的1 需要往前按照一定的增量去比较，
和9 比较交换位置为     ======>      7,1,0,2,3,1,6,5,8,4,9
此时1 和7比较，交换位置后为 ====>     1,1,0,2,3,7,6,5,8,4,9
第一次排序结束；

二. 5 /2 = 2 即增量为2时
{1,0,3,6,8,9}  {1,2,7,5,4}
对每一部分再进行直接插入排序，
0，1，1，2，3，7，6，5，8，4，9  此时{0,1,3,6,8,9} {1,2,7,5,4}

i加1 下标为3，此时2和第一个1进行比较， 不交换位置
i加1 下标为4，此时3和第二个1进行比较，不交换位置
i加1 下标为5，此时7和2进行比较， 不交换位置
i加1 下标为6，此时6和3进行比较，不交换位置
i加1 下标为7，  此时5和7进行比较，交换位置
0，1，1，2，3，5，6，7，8，4，9  此时{0,1,3,6,8,9} {1,2,5,7,4}
   再往前比较，发现是升序 开启下一轮比较
i加1 下标为8， 此时8和6进行比较， 不交换位置
i加1 下标为9 ，此时4和7进行比较，交换位置
0，1，1，2，3，5，6，4，8，7，9  此时{0,1,3,6,8,9} {1,2,5,4,7}
   往前比较，4和5进行比较，交换位置
   0，1，1，2，3，4，6，5，8，7，9  此时{0,1,3,6,8,9} {1,2,4,5,7}
  再往前比较，4和2进行比较，不交换位置

i加1 下标为10， 此时9和8进行比较， 不交换位置
第二次排序结束

三. 2/2 = 1
0，1，1，2，3，4，6，5，8，7，9 
参照上图中打印的  比较的两个数

6. 重点讲解

细心的你一定发现了 上面的步长采用的是折半法，其实希尔排序的核心在于如何选取步长,但是步长最优解至今还是个数学难题，至今没有解答
目前认为Knuth提出的 h= 3 x h + 1,生成的序列 求出的步长是最优秀
生成序列为 1，4，13，40，121，364....

    int h = 1;
    while (h < arr.count) {
        h = h * 3+ 1;
    }
   此时h为合理的步长序列最大值，在缩减增量的时候，则可以采用初始值 ：
  increment= h;
  increment = (increment -1)/3, 作为增量值，不过在网上很多采用的公式为  increment = increment/3 + 1

7. 稳定性

相对稳定的排序

参考1
参考2