iOS：常用排序算法

冒泡排序

冒泡排序是相邻数据进行两两比较，假设升序排序，则一趟排序下来，就会有一个最大数产生在数组最末端。因为有 n 个数据需要进行比较，而每一趟排序需要遍历n个数据，所以时间复杂度为O(n^2)

///> 对数组进行排序（时间复杂度：冒泡排序 O(n^2)）
-(void)maoPaoSortWithArr:(NSMutableArray *)arrM{
    //冒泡排序，需要相连两个数进行 两两比较。所以此处是 比较count-1次
    for (int i = 0; i<arrM.count-1; i++) {
        //内层循环：每次走完1次外循环，内层循环就减少1次，外层循环i次，内层循环就减少i次，所以比较次数是：count-1-i 次
        for (int j = 0; j<arrM.count-1-i; j++) {
            
            if ([arrM[j] integerValue] > [arrM[j+1] integerValue]) {
//            if (arrM[j] > arrM[j+1] ) { //注意：在OC中需要对此处强制进行比较int类型。经测试即使数组都是数字，这样操作冒泡排序结果也不对。
                
                id temp = arrM[j];
                arrM[j] = arrM[j+1];
                arrM[j+1] = temp;
            }
        }
        
    }

}
//调用测试：
   NSMutableArray * arrM = @[@6,@1,@2,@7,@9,@3,@4,@5,@10,@11,@8].mutableCopy;
     [self maoPaoSortWithArr:arrM];
     NSLog(@"maopao sort->%@",arrM);
//结果：
maopao sort->(
    1,
    2,
    3,
    4,
    5,
    6,
    7,
    8,
    9,
    10,
    11
)

冒泡排序结果.png

快速排序

快速排序是定下一个基准数（一般默认定义最左侧数据为基准数，可以理解为参照数），每一趟排序都需要从左（角标 i）右（角标 j）两侧开始像中间进行排序，因为基准数定义在左侧，一般先从右侧开始向左侧移动，j--；遇到小于基准数的暂停，左侧开始向右移动，i++；遇到大于基准数的暂停；然后交换i 和 j 所对应的数据。当i和j相遇的时候，则将相遇值与基准数进行交换，一趟排序结束。时间复杂度是O(log2 n)

///> 对数组进行排序（快速排序 O(log2n) (aha 算法修改)）  (修改了，结果对了)
-(void)quickSortWithArrM:(NSMutableArray *)arrM withLeft:(NSInteger)left withRight:(NSInteger)right{
    //两个哨兵 i j
    NSInteger i,j,temp;
    //两个临时变量，中间变量
//    id t,temp;
    
    if (left>=right) {
        return;
    }
    //定义基准数
    temp = [arrM[left] integerValue];
    
    //初始化时候赋值
    i= left;
    j = right;
    
    while (i < j) {
        //因为先定义基准值在 最左侧，所以先从 最右侧开始移动。
        while ([arrM[j] integerValue]>= temp && i<j) {
            j--;
        }
        if(i==j){
            break;
        }
        arrM[i++] = arrM[j];
        
        
        while ([arrM[i] integerValue] <= temp && i<j) {
            i++;
        }
        
        if(i==j){
            break;
        }
        arrM[j--] = arrM[i];
        

        
    }
    
    //到此，跳出while 循环，说明 i和j相遇。 -》此时应该将 相遇处的数组值 与初始化时的 基准数 进行交换。 完成一趟排序。
    arrM[i] = [NSNumber numberWithInteger:temp];
    
    //到此，完成第一趟 排序。
    
    //递归排序左边 和 右边
    [self quickSortWithArrM:arrM withLeft:left withRight:i];
    [self quickSortWithArrM:arrM withLeft:i+1 withRight:right];
    
    
}

//测试：
NSMutableArray * arrM = @[@6,@1,@2,@7,@9,@3,@4,@5,@10,@11,@8].mutableCopy;
    [self quickSortWithArrM:arrM withLeft:0 withRight:arrM.count-1];
    NSLog(@"quick sort->%@",arrM);

//结果：
quick sort->(
    1,
    2,
    3,
    4,
    5,
    6,
    7,
    8,
    9,
    10,
    11
)

快速排序结果.png