###素数（质数） 质数又称素数，是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数

算法：对正整数n，如果用2到 sqrt（n）之间的所有整数去除，均无法整除，则n为质数。

sqrt（n）求n的平方根，就是n开平方

- (BOOL)isPrime:(NSInteger)num {
    for(int i = 2;i< sqrt(num);i++) {
        if (num % i == 0) {
            return NO;
        }
    }
    return YES;
}

###最大公约数，最大公因数，最小公倍数 如果数a能被数b整除，a就叫做b的倍数，b就叫做a的约数。

最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个

a * b / 最大公约数 = 最小公倍数

- (NSInteger)maxgcd:(NSInteger)a aNum:(NSInteger)b {
    // 保证a > b
    if (a < b) {
        NSInteger temp = a;
        a = b;
        b = temp;
    }
    if (a %b == 0) {
        return b;
    }
    NSInteger k = 1;
    while (k!= 0) {
        k = a % b;
        a = b;
        b = k;
    }
    return a;
}

###给定一个字符串，输出本字符串中只出现一次并且最靠前的那个字符的位置？ //如“abaccddeeef”,字符是b,输出应该是2

- (NSInteger )subStringFirstShow:(NSString *)str {
    NSInteger firstIndex = -1;
    NSMutableArray *sameArray = [NSMutableArray arrayWithCapacity:0];
    for (int i = 0; i< str.length; i++) {
        NSString *aStr = [str substringWithRange:NSMakeRange(i, 1)];

        if ([sameArray containsObject:aStr]) {
            continue;
        }
        if(firstIndex >= 0 && firstIndex < str.length) {
            break;
        }

        NSInteger index = i+1;
        for (int j = i+1; j < str.length; j++) {
            NSString *bStr = [str substringWithRange:NSMakeRange(j, 1)];
            if ([aStr isEqualToString:bStr]) {
                [sameArray addObject:aStr];
                break;
            } else {
                index ++;
                if (index == str.length) {
                     firstIndex = i;
                    break;
                }
            }

        }
    }
    return firstIndex + 1;
}

###冒泡排序

重复地走访过要排序的数列，采用相邻比较交换的方法，如果他们的顺序错误就把他们交换过来。

通过一遍走访就把最大的数据放到了最后一个位置，然后继续走头走访剩余的length-i。个元素，找到第i大元素，以此类推，就好像气泡慢慢的浮出水面，所以叫冒泡排序。

//冒泡排序(降序 -从大到小)
- (void)maoPaoSort: (NSMutableArray *)array {
    for (int i = 0; i< array.count; i++) {
        for (int j = i+1; j< array.count; j++) {
            if([array[i] integerValue] < [array[j] integerValue]) {
                [array exchangeObjectAtIndex:i withObjectAtIndex:j];
            }
        }
    }
}

###选择排序 直接在每趟i+1～length的元素直接找到最小元素的array[j]的位置k；将array[j]放到正确的位置k即可

// 选择排序 (从大到小)
- (void)selectSort:(NSMutableArray *)array {
    for (int i = 0; i< array.count;i++) {
        NSInteger maxNum = [array[i] integerValue];
        int index = i;
        for (int j = i+1; j< array.count; j++) {
            if (maxNum < [array[j] integerValue]) {
                maxNum = [array[j] integerValue];
                index = j;
            }
        }
        if (index != i) {
            [array exchangeObjectAtIndex:index withObjectAtIndex:i];
        }
    }
}

###直接插入排序(Insertion Sort)

基本思想是：在已排序好的i-1个记录中，先找到第i个元素的位置j(将所以比i大的通通后移一位，就可以空出那个合适的位置j）)，然后将第i个元素放到此为止即可

// 直接插入排序（从大到小）
- (void)insertSort:(NSMutableArray *)array {
    for (int i = 1; i< array.count; i++) {
        int j = i-1;
        NSNumber *temp = array[i];
        // 比temp小的全部后移
        while (j>= 0 && [array[j] integerValue] < [temp integerValue]) {
            [array replaceObjectAtIndex:j+1 withObject:array[j]];
            j--;
        }
        [array replaceObjectAtIndex:j+1 withObject:temp];
    }
}

###快速排序 思想：以第一个元素作为临界值，将所有比它小的，放入左侧，所有比它大的，放到右侧，然后对左右2个小数组，继续按此规律排序

做法： 1.左右2个指针low和high，分别指向数组的a[0]和a[count-1], 以a[0]为临界值mid。

2.从右向左查找第一个比临界值小的元素，也就是a[high] > mid ,high--。

3.从左向右查找第一个地临界值大的元素，也就是a[low] <= mid ,low++。 4.执行完2.3（如果low < high） 交换low与high

5.将临界值赋值给low，low就是临界值的正确位置

6.被临界值划分的2个数据继续1～5

// 从小到大
- (void)quickSort:(NSMutableArray *)array low:(NSInteger)lowIndex hight:(NSInteger)hightIndex {
    if (lowIndex < hightIndex) {
        NSInteger L = lowIndex;
        NSInteger r = hightIndex;
        NSInteger mid = [array[lowIndex] integerValue];
        while (L < r ) {
            //从右找比mid小的数字
            while( L < r && [array[r] integerValue] > mid) {
                r--;
            }
            while (L < r && [array[L] integerValue] <= mid) {
                L++;
            }
            if (L< r) {
                [array exchangeObjectAtIndex:L withObjectAtIndex:r];
            }
        }
        [array exchangeObjectAtIndex:lowIndex withObjectAtIndex:L];
        [self quickSort:array low:lowIndex hight:(L - 1)];
        [self quickSort:array low:(L + 1) hight:hightIndex];
    }
}

###阶乘 一个正整数的阶乘（factorial）是所有小于及等于该数的正整数的积，

并且0的阶乘为1。 自然数n的阶乘写作n!

- (NSInteger) someSum:(NSInteger)a {
    if (a <=1 && a>=0){
        return 1;
    }
    NSInteger sub = 1;
    for (int i = 1; i<= a; i++) {
        sub = sub * i;
    }
    return sub;
}

###字符串逆序

- (NSString *)reverse:(NSString *)aStr {
    NSMutableArray *aArray = [NSMutableArray arrayWithCapacity:0];
    for (NSInteger i = aStr.length - 1; i >= 0; i--) {
        [aArray addObject:[aStr substringWithRange:NSMakeRange(i, 1)]];
    }
    return [aArray componentsJoinedByString:@""];
}

###二叉树的遍历 二叉树的遍历是指从根结点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。

已知前序遍历和后序遍历，无法确定一颗唯一的二叉树

前序：跟左右

中序：左跟右

后序：左右跟

二分查找（在有序队列中的查找）

是一种算法，其输入是一个有序的元素列表（必须是有序的），如果查找的元素包含在列表中，二分查找返回其位置，否则返回NULL

L<h的情况下每次取mid元素与搜素shu

- (NSInteger) binarySearch:(NSMutableArray *)sortArray num:(NSInteger)searchNum {
    NSInteger count = 0;
    NSInteger low = 0;
    NSInteger high = sortArray.count -1;
    if (searchNum < [sortArray[low] integerValue] || searchNum > [sortArray[high] integerValue]) {
        NSLog(@"fail");
    }
        while (low < high) {
        NSInteger mid = (low + high)/2;
        count ++;
        NSLog(@"%ld----%ld----%ld ---%ld",(long)count,(long)[sortArray[low] integerValue],(long)[sortArray[high] integerValue], [sortArray[mid] integerValue]);
        if ( [sortArray[mid] integerValue] == searchNum) {

            return count;
        } else {
            if ([sortArray[mid] integerValue] > searchNum) {
                high = mid-1;
            } else {
                low = mid+1;
            }
        }
    }
    return count;
}

###模拟栈的实现-NSArray 栈是一种数据结构，特点：先进后出，

使用拥有NSMutableArray的oc对象来模拟，

先进后出就是pop出来的是lastobject，

从栈底便利是enumerateObjectsWithOptions:NSEnumerationConcurrent

从栈顶便利是 [self.stackArray enumerateObjectsWithOptions:NSEnumerationReverse

###给定两个排好序的数组A,B,请写一个函数,从中找出他们的公共元素:findCommon(A,B)

- (NSMutableArray *)findCommon:(NSMutableArray*)bArray array:(NSMutableArray  *)aArray {
    NSMutableArray *array = [NSMutableArray arrayWithCapacity:0];
    int index = 0;
    BOOL bAsce = YES;
    if (bArray.count >=2) {
        if ([bArray[0] integerValue] > [bArray[1] integerValue]) {
            bAsce = NO;
        }
    }
    for (int i = 0; i< bArray.count; ) {
        NSInteger temp = [bArray[i] integerValue];
        if (index >= aArray.count) {
            return array;
        }
        for (int j = index; j< aArray.count;) {
            NSInteger bTemp = [aArray[j] integerValue];
            if (bTemp == temp) {
                [array addObject:aArray[j]];
                 j++;
                index = j;
                i++;
                break;
            } else {

                if (bTemp > temp) {
                    if (bAsce) {
                        i++;
                        break;
                    } else {
                        j++;
                    }
                } else {
                    if (bAsce) {
                        j++;
                    } else {
                        i++;
                        break;
                    }
                }
            }
        }
    }
    return array;
}