iOS 算法之排序、查找、递归

1.冒泡排序（依次循环旁边的比较放到后边去）

冒泡排序是通过比较两个相邻元素的大小实现排序，如果前一个元素大于后一个元素，就交换这两个元素。这样就会让每一趟冒泡都能找到最大一个元素并放到最后。

/**
 最好时间复杂度是O(n)
 最坏时间复杂度是O(n^2)
平均时间复杂度：O(n^2)
平均空间复杂度：O(1)
 */
+ (NSArray *)bubbleSort:(NSArray *)unsortDatas {
    NSMutableArray *unSortArray = [unsortDatas mutableCopy];
    for (int i = 0; i < unSortArray.count -1 ; i++) {
        BOOL isChange = NO;
        for (int j = 0; j < unSortArray.count - 1 - i; j++) {
            // 比较相邻两个元素的大小，后一个大于前一个就交换
            if ([unSortArray[j] integerValue] > [unSortArray[j+1] integerValue]) {
                NSNumber *data = unSortArray[j+1];
                unSortArray[j+1] = unSortArray[j];
                unSortArray[j] = data;
                isChange = YES;
            }
        }
        if (!isChange) {
            // 如果某次未发生数据交换，说明数据已排序
            break;
        }
    }
    return [unSortArray copy];
}

2.选择排序（拿前边的和后边的依次比较放到前边去，就是先排好前边的）

/**
 最好时间复杂度是O(n)
 最坏时间复杂度是O(n^2)
平均时间复杂度：O(n^2)
平均空间复杂度：O(1)
 */
+ (NSArray *)seelectSort:(NSArray *)unsortDatas {
    NSMutableArray *unSortArray = [unsortDatas mutableCopy];
    for (int i = 0; i < unSortArray.count; i++) {
        int mindex = i;
        for (int j = i; j < unSortArray.count; j++) {
            // 找到最小元素的index
            if ([unSortArray[j] integerValue] < [unSortArray[mindex] integerValue]) {
                mindex = j;
            }
        }
        // 交换位置
        NSNumber *data = unSortArray[i];
        unSortArray[i] = unSortArray[mindex];
        unSortArray[mindex] = data;
    }
    return [unSortArray copy];
}

3.选择排序（拿前边的和后边的依次比较放到前边去，就是先排好前边的）

/**
 最好时间复杂度是O(n)
 最坏时间复杂度是O(n^2)
平均时间复杂度：O(n^2)
平均空间复杂度：O(1)
 */
- (void)selectSortArray:(NSMutableArray *)array {
    for (int i = 0; i < array.count-1; i++) {
        for (int j = i+1; j < array.count; j++) {
            if (array[i] > array[j]) {
                id tmp = array[i];
                array[i] = array[j];
                array[j] = tmp;
            }
        }
    }
}

4.插入排序

插入排序简单直观，通过构建有序序列，对于未排序的元素，在已排序序列中从后向前扫描，找到相应位置并插入。时间复杂度为 O(n^2) ，原地排序，额外空间复杂度为 O（1）。

过程分为 6 个步骤：

从第一个元素开始，该元素可以认为已经被排序
取出下一个元素，在已经排序的元素序列中从后向前扫描
如果该元素（已排序）大于新元素，将该元素移到下一位置
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到该位置后
重复步骤2~5

+ (NSArray *)insertionSort:(NSArray *)unsortDatas {
    NSMutableArray *unSortArray = [unsortDatas mutableCopy];
    int preindx = 0;
    NSNumber *current;
    for (int i = 1; i < unSortArray.count; i++) {
        preindx = i - 1;
        // 必须记录这个元素，不然会被覆盖掉
        current = unSortArray[i];
        // 逆序遍历已经排序好的数组

        // 当前元素小于排序好的元素，就移动到下一个位置
        while (preindx >= 0 && [current integerValue] < [unSortArray[preindx] integerValue] ) {
            // 元素向后移动
            unSortArray[preindx+1] = unSortArray[preindx];
            preindx -= 1;
        }
        // 找到合适的位置，把当前的元素插入
        unSortArray[preindx+1] = current;
    }
    return [unSortArray copy];
}

5.希尔排序

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。`

增量：插入排序只能与相邻的元素进行比较，而希尔排序则是进行跳跃比较，而增量就是步长。

/**
 最优的增量在最坏的情况下却为O(n²⁄³)，最坏的情况下时间复杂度仍为O(n²)
 需要注意的是，增量序列的最后一个增量值必须等于1才行
 另外由于记录是跳跃式的移动，希尔排序并不是一种稳定的排序算法
 */
- (void)shellSortArray:(NSMutableArray *)array {
    int count = (int)array.count;
    // 初始增量为数组长度的一半，然后每次除以2取整
    for (int increment = count/2; increment > 0; increment/=2) {
        // 初始下标设为第一个增量的位置，然后递增
        for (int i = increment; i<count; i++) {
            // 获取当前位置
            int j = i;
            // 然后将此位置之前的元素，按照增量进行跳跃式比较
            while (j-increment>=0 && [array[j] integerValue]<[array[j-increment] integerValue]) {
                [array exchangeObjectAtIndex:j withObjectAtIndex:j-increment];
                j-=increment;
            }
        }
    }
}

6.快速排序(稳定: 否)

/**
 最理想情况算法时间复杂度O(nlogn)，最坏O(n^2),平均O(nlogn)
平均空间复杂度：O(nlogn)       O(nlogn)~O(n^2)
 */
- (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];
}

7.堆排序

堆
堆（英语：heap)是计算机科学中一类特殊的数据结构的统称
堆总是满足下列性质：1. 堆中某个节点的值总是不大于或不小于其父节点的值；2. 堆总是一棵完全二叉树
将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆

完全二叉树
若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

/**
 时间复杂度为O(nlogn)
 */
- (void)heapSortArray:(NSMutableArray *)heapList len:(NSInteger)len {
    // 建立堆，从最底层的父节点开始
    for(NSInteger i = (heapList.count/2 -1); i>=0; i--)
        [self adjustHeap:heapList location:i len:heapList.count];
    
    for(NSInteger i = heapList.count -1; i >= 0; i--){
        NSInteger maxEle = ((NSString *)heapList[0]).integerValue;
        heapList[0] = heapList[i];
        heapList[i] = @(maxEle).stringValue;
        
        [self adjustHeap:heapList location:0 len:i];
    }
}

- (void)adjustHeap:(NSMutableArray *)heapList location:(NSInteger)p len:(NSInteger)len {
    NSInteger curParent = ((NSString *)heapList[p]).integerValue;
    NSInteger child = 2*p + 1;
    while (child < len) {
        // left < right
        if (child+1 < len && ((NSString *)heapList[child]).integerValue < ((NSString *)heapList[child+1]).integerValue) {
            child ++;
        }
        if (curParent < ((NSString *)heapList[child]).integerValue) {
            heapList[p] = heapList[child];
            p = child;
            child = 2*p + 1;
        }
        else
            break;
    }
    heapList[p] = @(curParent).stringValue;
}

8.归并排序(稳定: 是)

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

/**
 时间复杂度:
最优时间: O(nlog(n))
最坏时间: O(nlog(n))
平均时间: O(nlog(n))
（1）“分解”——将序列每次折半划分
（2）“合并”——将划分后的序列段两两合并后排序
 */
- (NSArray *)mergeSortArray:(NSMutableArray *)array {
    // 排序数组
    NSMutableArray *tempArray = [NSMutableArray arrayWithCapacity:1];
    // 第一趟排序是的子数组个数为ascendingArr.count
    for (NSNumber *num in array) {
        NSMutableArray *subArray = [NSMutableArray array];
        [subArray addObject:num];
        [tempArray addObject:subArray];
    }
    /**
     分解操作 每一次归并操作
     当数组个数为偶数时tempArray.count/2; 当数组个数为奇数时tempArray.count/2+1; 当tempArray.count == 1时，归并排序完成
     */
    while (tempArray.count != 1) {
        NSInteger i = 0;
        
        // 当数组个数为偶数时 进行合并操作， 当数组个数为奇数时，最后一位轮空
        while (i < tempArray.count - 1) {
            
            // 将i 与i+1 进行合并操作 将合并结果放入i位置上 将i+1位置上的元素删除
            tempArray[i] = [self mergeArrayFirstList:tempArray[i] secondList:tempArray[i + 1]];
            [tempArray removeObjectAtIndex:i + 1];
            
            // i++ 继续下一循环的合并操作
            i++;
        }
    }


    return tempArray.copy;
}
// 合并
- (NSArray *)mergeArrayFirstList:(NSArray *)array1 secondList:(NSArray *)array2 {
    
    // 合并序列数组
    NSMutableArray *resultArray = [NSMutableArray array];
    
    // firstIndex是第一段序列的下标 secondIndex是第二段序列的下标
    NSInteger firstIndex = 0, secondIndex = 0;
    
    // 扫描第一段和第二段序列，直到有一个扫描结束
    while (firstIndex < array1.count && secondIndex < array2.count) {
        // 判断第一段和第二段取出的数哪个更小，将其存入合并序列，并继续向下扫描
        if ([array1[firstIndex] floatValue] < [array2[secondIndex] floatValue]) {
            [resultArray addObject:array1[firstIndex]];
            firstIndex++;
        } else {
            [resultArray addObject:array2[secondIndex]];
            secondIndex++;
        }
    }
    // 若第一段序列还没扫描完，将其全部复制到合并序列
    while (firstIndex < array1.count) {
        [resultArray addObject:array1[firstIndex]];
        firstIndex++;
    }
    // 若第二段序列还没扫描完，将其全部复制到合并序列
    while (secondIndex < array2.count) {
        [resultArray addObject:array2[secondIndex]];
        secondIndex++;
    }
    // 返回合并序列数组
    return resultArray.copy;
}

9.二分查找

/**
 二分查找法只适用于已经排好序的查找
 */
- (NSInteger)dichotomySearch:(NSArray *)array target:(id)key {
    NSInteger left = 0;
    NSInteger right = [array count] - 1;
    NSInteger middle = [array count] / 2;
    
    while (right >= left) {
        middle = (right + left) / 2;
        
        if (array[middle] == key) {
            return middle;
        }
        
        if (array[middle] > key) {
            right = middle - 1;
        }else if (array[middle] < key) {
            left = middle + 1;
        }
    }
    return -1;
}

10.递归

斐波那契数列问题
- (NSInteger)recursion0:(NSInteger) n {
    if (n <= 1) return n;
    return [self recursion0:n-1] + [self recursion0:n-2];
}

阶乘
- (NSInteger)recursion1: (NSInteger)n {
    if (n == 0) { //递归边界
        return 1;
    }
    return n*[self recursion1:(n-1)];//递归公式
}