算法基础

不积跬步，无以至千里；不积小流，无以成江海

---

iOS开发中基本上用不到什么算法，但是在面试的时候又会经常问算法方面相关的。

在工作中冒泡排序用的比较多，一般面试反而问到底是快速排序，它的效率更高，需要掌握。

- (void)quickSortWithArr:(NSMutableArray *)arr left:(NSInteger)left right:(NSInteger)right{
    if (left >= right) return;
    NSInteger i = left;
    NSInteger j = right;
    NSInteger key = [arr[i] integerValue];
    while (i<j) {
        while (i<j && [arr[j] integerValue] >= key) {//从右侧找到第一个比key小的
            j--;
        }
        arr[i] = arr[j];
        while (i<j && [arr[i] integerValue] <= key) {//从左边找到第一个比key大的
            i++;
        }
        arr[j] = arr[i];
    }
    arr[i] = [NSNumber numberWithInteger:key];
    [self quickSortWithArr:arr left:left right:i-1];
    [self quickSortWithArr:arr left:i+1 right:right];
}

另外一个常用到的是递归的思想，在工作中也会经常遇到，自己调用自己。其实上述快排就已经用到了递归。一个经典的题目N的阶乘（0的阶乘是1，负数没有阶乘）。

- (NSInteger)recursionFactorialWithNum:(NSInteger)num{
    if (num == 0) {
        return 1;
    }else{
        return num * [self recursionFactorialWithNum:num-1];
    }
}

这两个比较有代表意义，先写这两个，想到了新的再补充

---

跑得慢，听到的是骂声； 跑得快，听到的就只是风声

---