基本排序算法-冒泡排序、选择排序、插入排序

1.冒泡排序

原理：冒泡排序的原理就是小的数字慢慢的往上浮。从数组最后面开始循环，如果一个数比它前面数小，则交换两者位置。

以下是冒泡排序OC语言完整实现：

/*冒泡排序*/
+ (void)startSortWithDataArray{
    NSArray *array = @[@8,@3,@5,@10,@1,@6,@4,@2,@7,@9];
    NSMutableArray *arr = [array mutableCopy];

    //交换次数
    NSInteger exchangeCount = 0;
    //比较次数
    NSInteger checkCount = 0;
    //标记有没有发生交换，如果没有发生则表示数组已经有序，退出排序
    BOOL haveChange = false;

    for (NSInteger i = 0; i < arr.count; i++) {
        haveChange = false;
        for (NSInteger j = 0; j < arr.count - 1 - i; j++) {

            if ([arr[j] integerValue] > [arr[j+1] integerValue]) {
                [arr exchangeObjectAtIndex:j withObjectAtIndex:j+1];
                exchangeCount++;
                haveChange = true;
            }
            checkCount++;
            if (j == arr.count - 2 - i) {
                if (!haveChange) {
                    NSLog(@"----------本趟结束，且本趟没有进行交换，数组已经有序，退出排序-------\n\n");
                }
            }
        }
        if (haveChange == false) {
            break;
        }
    }

    NSLog(@"排序后：%@",arr);
    NSLog(@"本次排序结束，一共比较%ld次，共进行%ld次交换",checkCount,exchangeCount);
}

时间复杂度：O(N²) 　　
1.平均情况下：冒泡比较的次数约是插入排序的两倍，移动次数一致。
2.平均情况下：冒泡与选择排序的比较此时是一样的，移动比选择排序多出n次

稳定性：稳定

示意图： 冒泡排序

2.选择排序

原理：选择排序的原理很简单，就是从需要排序的数据中选择最小的（从小到大排序），然后放在第一个，选择第二小的放在第二个。

以下是选择排序OC语言完整实现：

/*选择排序*/
+ (void)startSortWithDataArray{
    NSArray *array = @[@8,@3,@5,@10,@1,@6,@4,@2,@7,@9];
    NSMutableArray *arr = [array mutableCopy];

    //交换次数
    NSInteger exchangeCount = 0;
    //比较次数
    NSInteger checkCount = 0;

    for (NSInteger i = 0 ; i < arr.count; i++) {
        NSInteger minIndex = i;
        for (NSInteger j = i+1; j < array.count; j++) {
            checkCount++;
            if ([arr[j]integerValue] < [arr[minIndex]integerValue]) {
                 minIndex = j;
            }
        }
        if (minIndex != i) {
            [arr exchangeObjectAtIndex:i withObjectAtIndex:minIndex];
            exchangeCount++;
        }
    }

    NSLog(@"排序后：%@",arr);
    NSLog(@"本次排序结束，一共比较%ld次，共进行%ld次交换",checkCount,exchangeCount);
}

时间复杂度：O(N²) 　　稳定性：不稳定
运行时间与输入无关。因为前一次的扫描并不能为后面的提供信息。
数据的移动次数是最小的。

示意图： 选择排序

3.插入排序

原理：如果数组进行循环得到a，若a比a前面的一个数小，则a就与前面数交换位置（相当于a向前面移动一位），若移动后a任然比前面一个数小，则再向前移动一位。

以下是插入排序OC语言完整实现：

/*插入排序*/
+ (void)startSortWithDataArray{
    NSArray *array = @[@8,@3,@5,@10,@1,@6,@4,@2,@7,@9];
    NSMutableArray *arr = [array mutableCopy];

    //比较次数
    NSInteger checkCount = 0;
    //交换次数
    NSInteger exchangeCount = 0;

    for (NSInteger i = 1; i < .count; i++) {
        for (NSInteger j = i; j > 0 ; j--) {
            checkCount++;
            if ([arr[j]integerValue] < [arr[j-1]integerValue]) {
                [arr exchangeObjectAtIndex:j withObjectAtIndex:j-1];
                exchangeCount++;
            }else{
                NSLog(@"本次不交换，本趟排序结束\n");
                break;
            }
        }
    }
    NSLog(@"排序后：%@",arr);
    NSLog(@"插入排序结束，一共比较%ld次，共进行%ld次交换",checkCount,exchangeCount);
}
     

时间复杂度：O(N²) 　　稳定性：稳定
若数据倒置的数量很少时，速度快

示意图： 插入排序

图片出处：https://www.cnblogs.com/xiaohuiduan/p/11188304.html