OC中的排序算法

目录

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

    NSMutableArray *arr = [NSMutableArray array];
    for (int i = 0; i < 10; i++) {
        [arr addObject:@(arc4random() % 10)];
    }

冒泡

//冒泡排序
/*
 第i个元素和第i+1个元素比较，如果左边大于右边，进行交换
 */
- (void)maopao:(NSMutableArray *)arr {
    for (int i = 0; i < arr.count - 1; i++) {   //因为是两两比较，执行n-1次就可以判断到全部元素
        for (int j = 0; j < arr.count - 1 - i; j++) {
            NSInteger this = [arr[j] integerValue];
            NSInteger next = [arr[j+1] integerValue];
            if (this > next) {
                [arr exchangeObjectAtIndex:j withObjectAtIndex:j+1];
            }
        }
    }
}

快排

//快速排序
/*
 代码参考链接：http://developer.51cto.com/art/201403/430986.htm
 视频链接：http://www.iqiyi.com/v_19rrhzyeqs.html    有动画讲解，生动形象
 
 描述：
 取一个基准数，从右边开始算找到一个大于等于它的值，记录指针，及该元素索引，
 接着从左边开始算找到一个小于等于它的值，记录指针，
 当两个指针不重合的时候交换这两个位置对应的元素，进行了一次排序，
 直到两个指针重合时，重合位置的值必定小于等于基准数，因为是从右边开始算，将指针对应的值填入基准数原来位置，基准数填入指针对应位置，这样就完成了一次排序
 接着递归指针为中心的两个区间，完成排序
 */
- (void)kuaisu:(NSMutableArray *)arr {
    [self quickSort:arr left:0 right:(int)arr.count-1];
}

- (void)quickSort:(NSMutableArray *)arr left:(NSInteger)left right:(NSInteger)right {
    NSInteger i,j,temp;  //声明左右指针，基准数
    if (left > right) return;
    
    temp = [arr[left] integerValue];    //取第一个元素做基准数
    
    i = left;   //指针分别从最左和最右开始
    j = right;
    
    while (i != j) {    //指针碰撞结束循环
        //先从右边开始（为什么从右边开始，参考:http://blog.csdn.net/w282529350/article/details/50982650）
        while ([arr[j] integerValue] >= temp && i < j) { //快速排序是不稳定排序，所以加=
            j--;
        }
        //再从左边开始
        while ([arr[i] integerValue] <= temp && i < j) {
            i++;
        }
        //指针不同时交换对应元素在数组中的位置
        if (i < j) {
            [arr exchangeObjectAtIndex:i withObjectAtIndex:j];
        }
    }
    
    //将指针碰撞对应的元素填入基准数原来的位置,将基准数填入指针碰撞的索引位置
    [arr replaceObjectAtIndex:left withObject:arr[i]];
    [arr replaceObjectAtIndex:i withObject:@(temp)];
    
    //将两边区间进行递归操作
    [self quickSort:arr left:left right:i-1];
    [self quickSort:arr left:i+1 right:right];
}

选择

//选择排序
/*
 取出数组中的最小值，放到数组的第一个位置，
 从i=0开始，因为前面i个元素已经排好序，所以每取一个值就跳过数组前i个元素，直到最后一个元素不用判断就可以知道是最大值
 */
- (void)xuanzhe:(NSMutableArray *)arr {

    NSInteger index = 0;    //标记索引，从第一个开始
    
    for (int i = 0; i < arr.count - 1; i++) {   //最后一个元素不用比较就知道是最大，所以-1

        NSInteger min = [arr[i] integerValue];  //取第一个元素暂定为最小值
        for (int j = i + 1; j < arr.count; j++) {   //拿第一个数比较第二个数，所以+1，防止arr[j]比较arr[j]
            NSInteger num = [arr[j] integerValue];
            if (num <= min) {   //这里加=号，是关于不稳定排序的处理http://www.cnblogs.com/codingmylife/archive/2012/10/21/2732980.html
                min = num;
                index = j;
            }
        }
        [arr exchangeObjectAtIndex:index withObjectAtIndex:i];
    }
}

插入

//插入排序
/*
 从第二个数开始取出，与前面已排序的元素进行比较。因为待排元素被取出，此时空了一个位置
 当前一位元素大于待排元素，把前一位元素向后移一位，即填到待排元素被取出的位置，此时该元素被移动，再次空了一个位置
 直到前一位元素小于待排元素时，前一位元素不变，待排元素插入到空出的位置
 重复以上操作直到最后一个元素
 要注意的是待排元素是与前一位元素开始比较，比较方向为右边到左边
 */
- (void)charu:(NSMutableArray *)arr {
    for (int i = 1; i < arr.count; i++) {
        NSInteger indexNum = [arr[i] integerValue];   //从第二个数开始，与前面已排序的元素比较

        int j = i - 1;  //前面已排序的元素个数
        while (j >=0 && [arr[j] integerValue] > indexNum) { //前面的元素大于待排元素时
            [arr replaceObjectAtIndex:j+1 withObject:arr[j]];   //将前一个元素移到后面以一位
            j--;
        }
        [arr replaceObjectAtIndex:j+1 withObject:@(indexNum)];  //判断到前面的元素小于待排元素时，插入
    }
}