第二讲 简单排序

冒泡排序

简单来讲，就是依次比较相邻的两个数，将小数放在前面，大数放在后面，即交换两个数的位置。
ex：@[@(49),@(38),@(65),@(97),@(76),@(13),@(27),@(33)]
第1次排序：@[@(38),@(49),@(65),@(76),@(13),@(27),@(33),@(97)]
第2次排序：@[@(38),@(49),@(65),@(13),@(27),@(33),@(76),@(97)]
第3次排序：@[@(38),@(49),@(13),@(27),@(33),@(65),@(76),@(97)]
第4次排序：@[@(38),@(13),@(27),@(33),@(49),@(65),@(76),@(97)]
第5次排序：@[@(13),@(27),@(33),@(38),@(49),@(65),@(76),@(97)]

代码实现：

#pragma mark - 冒泡排序
- (NSArray *)bubbleSort:(NSArray *)array{
    NSMutableArray * temp = [NSMutableArray arrayWithArray:array];
    for(int i = 0;i < temp.count;i++){
        for (int j = 0 ; j < temp.count - 1 - i; j++) {
            if(temp[j] > temp[j+1]){
                id tmp = temp[j];
                temp[j] = temp[j+1];
                temp[j+1] = tmp;
            }
        }
    }
    NSLog(@"冒泡排序 ------------- > %@",temp);
    return temp;
}

打印结果：

冒泡排序 ------------- > (
    13,
    27,
    33,
    38,
    49,
    65,
    76,
    97
)

插入排序

基本思想是每一步将一个待排序的数据，插入到前面已经排好序的有序序列中去，直到插完所有元素为止。

#pragma mark - 插入排序
- (NSArray *)insertSort:(NSArray *)array{
    NSMutableArray * temp = [NSMutableArray arrayWithArray:array];
    for(int i = 1;i < temp.count;i++){
        int j = i;
        while (j>0 && temp[j]<temp[j-1]) {
            id tmp = temp[j];
            temp[j] = temp[j-1];
            temp[j-1] = tmp;
            j--;
        }
    }
    NSLog(@"插入排序 ------------- > %@",temp);
    return temp;
}

打印结果：

插入排序 ------------- > (
    13,
    27,
    33,
    38,
    49,
    65,
    76,
    97
)

选择排序

基本思想：初始时在序列中找到最小（大）元素，放到序列的起始位置作为已排序序列；然后，再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

#pragma mark - 选择排序
- (NSArray *)selectSort:(NSArray *)array{
    NSMutableArray * temp = [NSMutableArray arrayWithArray:array];
    for(int i = 1;i < temp.count;i++){
        int min = i;
        for (int j = i+1; j < temp.count; j++) {
            if (temp[j] < temp[i]) {
                min = j;
            }
        }
        if (min != i) {
            id tmp = temp[i];
            temp[i] = temp[min];
            temp[min] = tmp;
        }
    }
    NSLog(@"选择排序 ------------- > %@",temp);
    return temp;
}

打印结果：

选择排序 ------------- > (
    13,
    27,
    33,
    38,
    49,
    65,
    76,
    97
)

三种排序方式的对比

排序方式	平均时间复杂度	空间复杂度	稳定性	复杂性
冒泡排序	o(n^2)	o(1)	稳定	简单
插入排序	o(n^2)	o(1)	稳定	简单
选择排序	o(n^2)	o(1)	不稳定	简单