1. 選擇排序:

--析:將第 i 小的元素放到 a[i] 之中。數(shù)組的第 i 個(gè)位置的左邊是 i 個(gè)最小的元素且它們不會(huì)再被訪問。
--首先，找到數(shù)組中最小的那個(gè)元素,其次,將它和數(shù)組的第一個(gè)元素交換位置(如果第一個(gè)元素就是最小元素那么它就和自己交換)。再次,在剩下的元素中找到最小的元素,將它與數(shù)組的第二個(gè)元素交換位置。如此往復(fù),直到將整個(gè)數(shù)組排序。這種方法叫做選擇排序,因?yàn)樗诓粩嗟剡x擇剩余元素之中的最小者。
--命題 A: 對(duì)于長(zhǎng)度為 N 的數(shù)組，選擇排序需要大約 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;
}