选择排序、冒泡排序、插入排序

选择排序

// 选择排序(升序) 标记最小值，循环比较，替换最小值
- (void)selectSort {
    NSMutableArray *arr = [NSMutableArray arrayWithArray:@[@2,@1,@5,@3,@4]];
    for (int i=0; i<arr.count; i++) {
        NSNumber *minNum = [arr objectAtIndex:i];
        NSInteger minIndex = i;
        for (int j=i+1; j<arr.count; j++) {
            if ([minNum integerValue] > [[arr objectAtIndex:j] integerValue]) {
                minNum = [arr objectAtIndex:j];
                minIndex = j;
            }
        }
        // 替换最小值
        [arr replaceObjectAtIndex:minIndex withObject:[arr objectAtIndex:i]];
        [arr replaceObjectAtIndex:i withObject:minNum];
    }
    NSLog(@"arr = %@",arr);
}

冒泡排序

// 冒泡排序(升序) 相邻2个值进行比较，把最大值移到后面，循环比较
// 原理
- (void)bubblingSort {
    NSMutableArray *arr = [NSMutableArray arrayWithArray:@[@2,@1,@5,@3,@4]];
    for (int i=0; i<arr.count; i++) {
        for (int j=0; j<arr.count - 1; j++) {
            if ([[arr objectAtIndex:j] integerValue] > [[arr objectAtIndex:j+1] integerValue]) {
                NSNumber *temp = [arr objectAtIndex:j];
                [arr replaceObjectAtIndex:j withObject:[arr objectAtIndex:j+1]];
                [arr replaceObjectAtIndex:j+1 withObject:temp];
                NSLog(@"%@",arr);
            }
        }
    }
    NSLog(@"arr = %@",arr);
}

如果一个元素比另一个元素大（小），那么就交换这两个元素的位置。重复这一比较直至最后一个元素。这一比较会重复n-1趟，每一趟比较n-j次，j是已经排序好的元素个数。每一趟比较都能找出未排序元素中最大或者最小的那个数字。这就如同水泡从水底逐个飘到水面一样。冒泡排序是一种时间复杂度较高，效率较低的排序方法。

// 最优的冒泡排序
- (void)bubblingSort {
    NSMutableArray *arr = [NSMutableArray arrayWithArray:@[@2,@1,@5,@3,@4]];
    for (int i=0; i<arr.count - 1; i++) {
        for (int j=0; j<arr.count - i - 1; j++) {
            if ([[arr objectAtIndex:j] integerValue] > [[arr objectAtIndex:j+1] integerValue]) {
                NSNumber *temp = [arr objectAtIndex:j];
                [arr replaceObjectAtIndex:j withObject:[arr objectAtIndex:j+1]];
                [arr replaceObjectAtIndex:j+1 withObject:temp];
                NSLog(@"%@",arr);
            }
        }
    }
    NSLog(@"arr = %@",arr);
}

插入排序

步骤：

• 认为第一个是排好的，从下一个位置开始取值
• 和前面的数值进行比较，找出所取值应该插入的位置
• 插入
• 这时取值位置以前的顺序是排好的，重复循环即可

// 插入排序(升序)
- (void)insetSort {
    NSMutableArray *arr = [NSMutableArray arrayWithArray:@[@2,@1,@5,@3,@4]];
    for (int i=1; i<arr.count; i++) {
        // 取出一个值
        NSInteger min = i;
        NSInteger temp = [[arr objectAtIndex:i] integerValue];
        [arr removeObjectAtIndex:i];
        for (int j=i-1; j>=0; j--) {
            if (temp < [[arr objectAtIndex:j] integerValue]) {
                min = j;
            }
        }
        // 找出i前面的插入位置
        [arr insertObject:[NSNumber numberWithInteger:temp] atIndex:min];
    }
    NSLog(@"%@",arr);
}

总结：

选择排序、冒泡排序、插入排序比较次数都是：1+2+3+...+(n-1) = n*n/2，时间复杂度是一样的