常用基础算法

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

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

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

/**
 最好时间复杂度是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;
            }
        }
    }
}

快速排序

/**
 最理想情况算法时间复杂度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];
}

二分查找

/**
 二分查找法只适用于已经排好序的查找
 */
- (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;
}

递归：

程序调用自身的编程技巧称为递归（ recursion）。
一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

构成递归需具备的条件：
子问题须与原始问题为同样的事，且更为简单；
不能无限制地调用本身，须有个出口，化简为非递归状况处理。

递归的缺点：
递归算法解题相对常用的算法如普通循环等，运行效率较低。因此，应该尽量避免使用递归，除非没有更好的算法或者某种特定情况，递归更为适合的时候。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。

其他

• 斐波那契数列问题

- (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)];//递归公式
}

• 数组求和

- (NSInteger)recursionWithArr:(NSArray *)arr start:(NSInteger)start end:(NSInteger)end {
    if(start==end)//递归边界
        return [arr[start] integerValue];
    return [arr[start] integerValue] + [self recursionWithArr:arr start:(start+1) end:end]; //递归公式
}

• 求数组元素的最大值

#define max(a,b) (a>b?a:b)
- (NSInteger)recursionForMaxWithArr:(NSArray *)arr start:(NSInteger)start end:(NSInteger)end {
    if(start==end) {
        return [arr[start] integerValue];
    }else if(start+1 == end) {//递归边界
        return max([arr[start] integerValue], [arr[end] integerValue]);
    }
    return max([arr[start] integerValue], [self recursionForMaxWithArr:arr start:(start+1) end:end]);//递归公式!!!
}