OC版-快速排序，希尔排序

1.快速排序

• 1.从序列中选择一个轴点元素（pivot），假设每次选择0位置的元素为轴点元素，
• 2.利用pivot将序列分割成两个子序列
  • A.将小于pivot的元素放在轴点左侧
  • B.将大于pivot的元素放在轴点右侧
  • C.等于轴点的元素放在哪一边都可以
• 3.将子序列进行第一步和第二步的操作，直到不能在分割（子序列中只剩下一个元素）

//快速排序
- (void)quickSortWithArray:(NSMutableArray *)array
{
    [self quickSortWithArray:array begin:0 end:(int)array.count];
}
- (void)quickSortWithArray:(NSMutableArray *)array begin:(int)begin end:(int)end
{
    if (end - begin < 2) return;
    
    int mid = [self privotIndexWithBegin:begin end:end array:array];
    [self quickSortWithArray:array begin:begin end:mid];
    [self quickSortWithArray:array begin:mid + 1 end:end];
}
- (int)privotIndexWithBegin:(int)begin end:(int)end array:(NSMutableArray *)array
{
    NSNumber *privotV = array[begin];
    end--;
    
    BOOL right = YES;
    while (begin < end) {
        
        if (right) {
            //从右侧开始比较
            if ([privotV integerValue] < [array[end] integerValue]) {
                end--;
            }else{
                array[begin] = array[end];
                begin ++;
                right = NO;
            }
        }else{
            //从左侧开始比较
            if ([privotV integerValue] < [array[begin] integerValue]) {
                array[end] = array[begin];
                end --;
                right = YES;
            }else{
                begin ++;
            }
        }
    }
    
    array[begin] = privotV;
    return begin;
}

2.希尔排序

• 1.首先把序列看成一个矩阵，分成m列，逐列进行排序
  • A.m从某个整数逐渐减为1
  • B.当m等于1时，整个序列将变得有序
• 2.希尔排序也叫做递减增量排序
• 3.矩阵的列数取决于步长序列（step sequence）
  • A.不同的步长序列，执行效率也不同

//希尔排序
- (void)shellSortWithArray:(NSMutableArray *)array
{
    NSMutableArray *stepArray = [self shellStepSquenceWithArray:array];
    for (int i = 0; i < stepArray.count; i ++) {
        int step = [stepArray[i] intValue];
        [self shellSortWithArray:array step:step];
    }
}
- (void)shellSortWithArray:(NSMutableArray *)array step:(int)step
{
    for (int col = 0; col < step; col ++) {
        
        //利用插入排序实现列排序（这里使用的是未优化的插入排序）
        for (int begin = col + step; begin < array.count; begin ++) {
            int current = begin;
            while (current > (step - 1)) {
                NSNumber *a = array[current];
                NSNumber *b = array[current - step];
                
                if ([a integerValue] < [b integerValue]) {
                    array[current] = b;
                    array[current - step] = a;
                    current = current - step;
                }else{
                    current = 0;
                }
            }
        }
        
        
    }
}
- (NSMutableArray *)shellStepSquenceWithArray:(NSMutableArray *)array
{
    NSMutableArray *stepArray = [[NSMutableArray alloc] init];
    int step = (int)array.count >> 1;
    while (step > 0) {
        step = step >> 1;
        [stepArray addObject:@(step)];
    }
    return stepArray;
}