算法(二)--排序

1. 选择排序:

--析:将第 i 小的元素放到 a[i] 之中。数组的第 i 个位置的左边是 i 个最小的元素且它们不会再被访问。
--首先，找到数组中最小的那个元素,其次,将它和数组的第一个元素交换位置(如果第一个元素就是最小元素那么它就和自己交换)。再次,在剩下的元素中找到最小的元素,将它与数组的第二个元素交换位置。如此往复,直到将整个数组排序。这种方法叫做选择排序,因为它在不断地选择剩余元素之中的最小者。
--命题 A: 对于长度为 N 的数组，选择排序需要大约 N2/2 次比较和 N 次交换。
- (void)viewDidLoad {
    [super viewDidLoad];
    NSArray *array = @[@3, @8, @2, @9, @6, @10, @18, @12];
    NSArray *selCompArray = [self selectionComparable:array];
    NSLog(@"selCompArray=============%@", selCompArray);
}
- (NSArray *)selectionComparable:(NSArray *)array {
    NSMutableArray *arrayM = [NSMutableArray array];
    for (NSNumber *num in array) {
        [arrayM addObject:num];
    }
    NSInteger N = arrayM.count;
    for (NSInteger i = 0; i<N; i++) {
        // 将a[i]和a[i+1..N]中最小的元素交换
        NSInteger min = i;  // 最小元素的索引
        for (NSInteger j = i+1; j<N; j++) {
            if (arrayM[j] < arrayM[i]) {
                min = j;
                [arrayM exchangeObjectAtIndex:i withObjectAtIndex:j];
            }
        }
    }
    NSArray *comparableArray = arrayM.copy;
    return comparableArray;
}

2. 插入排序

- (void)viewDidLoad {
    [super viewDidLoad];
    NSArray *array = @[@3, @8, @2, @9, @6, @10, @18, @12];
    NSArray *insertCompArray = [self InsertionComparable:array];
    NSLog(@"insertCompArray=============%@", insertCompArray);
}
- (NSArray *)InsertionComparable:(NSArray *)array {
    NSMutableArray *arrayM = [NSMutableArray array];
    for (NSNumber *num in array) {
        [arrayM addObject:num];
    }
    NSInteger N = arrayM.count;
    // 将array按升序排列
    for (NSInteger i = 1; i<N; i++) {
        // 将 a[i] 插入到 a[i-1]、a[i-2]、a[i-3]...之中
        for (NSInteger j = i; j>0 && arrayM[j] < arrayM[j-1]; j--) {
            [arrayM exchangeObjectAtIndex:j withObjectAtIndex:j-1];
        }
    }
    NSArray *comparableArray = arrayM.copy;
    return comparableArray;
}

3. 希尔排序

- (void)viewDidLoad {
    [super viewDidLoad];
    NSArray *array = @[@3, @8, @2, @9, @6, @10, @18, @12];
    NSArray *xiErCompArray = [self xiErComparable:array];
    NSLog(@"xiErCompArray=============%@", xiErCompArray);
}
- (NSArray *)xiErComparable:(NSArray *)array {
    NSMutableArray *arrayM = [NSMutableArray array];
    for (NSNumber *num in array) {
        [arrayM addObject:num];
    }
    NSInteger N = arrayM.count;
    NSInteger h = 1;
    while (h < N/3) {
        h = 3*h +1; // 1, 4, 13, 40, 121, 364, 1093, ...
        while (h >=1) {
            for (NSInteger i = h; i<N; i++) {
                for (NSInteger j = i; j >= h && array[j] < array[j-h]; j -= h) {
                    [arrayM exchangeObjectAtIndex:j withObjectAtIndex:j-h];
                }
            }
            h = h/3;
        }
    }
    NSArray *comparableArray = arrayM.copy;
    return comparableArray;
}