简单算法集

简单排序法

这种方式是最笨拙的排序方式 效率最低：
每次排序只能确定一个位置，直到倒数第二次 末尾的最小值1才显示到最后

- (void)logArray {
    NSMutableArray * arr = @[@16,@1,@2,@9,@7,@12,@5,@3,@8,@13,@10].mutableCopy;
    for (int i = 0; i < arr.count; i++) {
        for (int j = i+1; j < arr.count; j++) {
            if (arr[i] < arr[j]) {
                [arr exchangeObjectAtIndex:i withObjectAtIndex:j];
            }
        }
        [self logArr:arr];
    }
}

一、冒泡排序

比较相邻两个数，如果后面的比前面的小 则交换位置，然后再与后面的数比较

- (void)logArrayFunction {
    NSMutableArray * arr = @[@16,@1,@2,@9,@7,@12,@5,@3,@8,@13,@10].mutableCopy;
    
    for (int i = 0; i < arr.count; i++) {
        for (int j = (int)arr.count-2; j >= i; j--) {
            if (arr[j] > arr[j+1]) {
                [arr exchangeObjectAtIndex:j withObjectAtIndex:j+1];
            }
        }
    }
}

冒泡改良方式，避免初始就是排好的序列的方式 做过多的无用循环比较

- (void)logArrayFunctionNice {
    BOOL flag = YES;
    NSMutableArray * arr = @[@16,@1,@2,@9,@7,@12,@5,@3,@8,@13,@10].mutableCopy;
    
    for (int i = 0; i < arr.count && flag; i++) {
        flag = NO;
        for (int j = (int)arr.count-2; j >= i; j--) {
            if (arr[j] > arr[j+1]) {
                [arr exchangeObjectAtIndex:j withObjectAtIndex:j+1];
                flag = YES;
            }
        }
    }
}

二、插入排序法

拿后面一个数与前面的一个数做比较，如果满足则交换，然后再往前查找

- (void)logInsertionSortingArray {
    NSMutableArray * arr = @[@16,@1,@2,@9,@7,@12,@5,@3,@8,@13,@10].mutableCopy;
    for (int i = 1; i < arr.count; i++) {
        int j = i;  /* j是一个坑， 确定坑的位置，再把数从坑里取出来，注意顺序*/
        id temp = arr[i];  /* temp 是从坑里取数*/
        if (arr[i] < arr[i-1]) {  /* j > 0 防止越界。写&&前面效率更高*/
            temp = arr[i];
            while (j > 0 && [temp intValue] < [arr[j-1] intValue]) {
                arr[j] = arr[j-1];
                j--;
            }
            arr[j] = temp;
        }
    }
}

三、选择排序法

选择一个数，然后用这个数与后面的每一相比较直到遇到比它大的数 然后交换位置

- (void)logChooseArray {
    NSMutableArray * arr = @[@16,@1,@2,@9,@7,@12,@5,@3,@8,@13,@10].mutableCopy;
    int min = 0, arrCount = (int)arr.count;
    for (int i = 0; i < arrCount-1; i++) {
        min = i;  
        for (int j = i + 1; j < arrCount; j++) {  
            if (arr[min] > arr[j]) {  /*如果有小于当前的最小值的关键字*/
                min = j;  /*将此关键字的下标赋值给min*/
            }
        }
        if (i != min) {  /*若min不等于i，说明找到最小值，交换*/
            [arr exchangeObjectAtIndex:i withObjectAtIndex:min];
        }
    }
}
//每次循环打印结果如下
1 16 2 9 7 12 5 3 8 13 10
1 2 16 9 7 12 5 3 8 13 10
1 2 3 9 7 12 5 16 8 13 10
1 2 3 5 7 12 9 16 8 13 10
1 2 3 5 7 12 9 16 8 13 10
1 2 3 5 7 8 9 16 12 13 10
1 2 3 5 7 8 9 16 12 13 10
1 2 3 5 7 8 9 10 12 13 16
1 2 3 5 7 8 9 10 12 13 16
1 2 3 5 7 8 9 10 12 13 16
1 2 3 5 7 8 9 10 12 13 16

四、快速排序法

数组选第一个数，把比数小的放到数的左边，比数大的放到右边，结束后对左右两边的数组作重复处理即可。

- (void)quickSortArray:(NSMutableArray *)array withLeftIndex:(NSInteger)leftIndex andRightIndex:(NSInteger)rightIndex
{
    if (leftIndex >= rightIndex) {//如果数组长度为0或1时返回
        return ;
    }
    
    NSInteger i = leftIndex;
    NSInteger j = rightIndex;
    //记录比较基准数
    NSInteger key = [array[i] integerValue];
    
    while (i < j) {
        /**** 首先从右边j开始查找比基准数小的值 ***/
        while (i < j && [array[j] integerValue] >= key) {//如果比基准数大，继续查找
            j--;
        }
        //如果比基准数小，则将查找到的小值调换到i的位置
        array[i] = array[j];
        
        /**** 当在右边查找到一个比基准数小的值时，就从i开始往后找比基准数大的值 ***/
        while (i < j && [array[i] integerValue] <= key) {//如果比基准数小，继续查找
            i++;
        }
        //如果比基准数大，则将查找到的大值调换到j的位置
        array[j] = array[i];
        
    }
    
    //将基准数放到正确位置
    array[i] = @(key);
    
    /**** 递归排序 ***/
    //排序基准数左边的
    [self quickSortArray:array withLeftIndex:leftIndex andRightIndex:i - 1];
    //排序基准数右边的
    [self quickSortArray:array withLeftIndex:i + 1 andRightIndex:rightIndex];
}

    NSMutableArray * arr = @[@16,@1,@2,@9,@7,@12,@5,@3,@8,@13,@10].mutableCopy;
    [self quickSortArray:arr withLeftIndex:0 andRightIndex:arr.count-1];

参考地址