1.冒泡排序（依次循環(huán)旁邊的比較放到后邊去）

冒泡排序是通過(guò)比較兩個(gè)相鄰元素的大小實(shí)現(xiàn)排序杉辙，如果前一個(gè)元素大于后一個(gè)元素模捂，就交換這兩個(gè)元素。這樣就會(huì)讓每一趟冒泡都能找到最大一個(gè)元素并放到最后蜘矢。

/**
 最好時(shí)間復(fù)雜度是O(n)
 最壞時(shí)間復(fù)雜度是O(n^2)
平均時(shí)間復(fù)雜度：O(n^2)
平均空間復(fù)雜度：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++) {
            // 比較相鄰兩個(gè)元素的大小狂男，后一個(gè)大于前一個(gè)就交換
            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) {
            // 如果某次未發(fā)生數(shù)據(jù)交換，說(shuō)明數(shù)據(jù)已排序
            break;
        }
    }
    return [unSortArray copy];
}

2.選擇排序（拿前邊的和后邊的依次比較放到前邊去品腹，就是先排好前邊的）

/**
 最好時(shí)間復(fù)雜度是O(n)
 最壞時(shí)間復(fù)雜度是O(n^2)
平均時(shí)間復(fù)雜度：O(n^2)
平均空間復(fù)雜度：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.選擇排序（拿前邊的和后邊的依次比較放到前邊去岖食，就是先排好前邊的）

/**
 最好時(shí)間復(fù)雜度是O(n)
 最壞時(shí)間復(fù)雜度是O(n^2)
平均時(shí)間復(fù)雜度：O(n^2)
平均空間復(fù)雜度：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.插入排序

插入排序簡(jiǎn)單直觀，通過(guò)構(gòu)建有序序列舞吭，對(duì)于未排序的元素泡垃，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入羡鸥。時(shí)間復(fù)雜度為 O(n^2) 蔑穴，原地排序，額外空間復(fù)雜度為 O（1）惧浴。

過(guò)程分為 6 個(gè)步驟：

從第一個(gè)元素開(kāi)始存和，該元素可以認(rèn)為已經(jīng)被排序
取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描
如果該元素（已排序）大于新元素衷旅，將該元素移到下一位置
重復(fù)步驟3捐腿，直到找到已排序的元素小于或者等于新元素的位置
將新元素插入到該位置后
重復(fù)步驟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;
        // 必須記錄這個(gè)元素，不然會(huì)被覆蓋掉
        current = unSortArray[i];
        // 逆序遍歷已經(jīng)排序好的數(shù)組

        // 當(dāng)前元素小于排序好的元素柿顶，就移動(dòng)到下一個(gè)位置
        while (preindx >= 0 && [current integerValue] < [unSortArray[preindx] integerValue] ) {
            // 元素向后移動(dòng)
            unSortArray[preindx+1] = unSortArray[preindx];
            preindx -= 1;
        }
        // 找到合適的位置茄袖，把當(dāng)前的元素插入
        unSortArray[preindx+1] = current;
    }
    return [unSortArray copy];
}

5.希爾排序

希爾排序是把記錄按下標(biāo)的一定增量分組，對(duì)每組使用直接插入排序算法排序九串；隨著增量逐漸減少绞佩，每組包含的關(guān)鍵詞越來(lái)越多寺鸥，當(dāng)增量減至1時(shí)猪钮，整個(gè)文件恰被分成一組品山，算法便終止。`

增量：插入排序只能與相鄰的元素進(jìn)行比較烤低，而希爾排序則是進(jìn)行跳躍比較肘交，而增量就是步長(zhǎng)。

/**
 最優(yōu)的增量在最壞的情況下卻為O(n2?3)扑馁，最壞的情況下時(shí)間復(fù)雜度仍為O(n2)
 需要注意的是涯呻，增量序列的最后一個(gè)增量值必須等于1才行
 另外由于記錄是跳躍式的移動(dòng)，希爾排序并不是一種穩(wěn)定的排序算法
 */
- (void)shellSortArray:(NSMutableArray *)array {
    int count = (int)array.count;
    // 初始增量為數(shù)組長(zhǎng)度的一半腻要，然后每次除以2取整
    for (int increment = count/2; increment > 0; increment/=2) {
        // 初始下標(biāo)設(shè)為第一個(gè)增量的位置复罐，然后遞增
        for (int i = increment; i<count; i++) {
            // 獲取當(dāng)前位置
            int j = i;
            // 然后將此位置之前的元素，按照增量進(jìn)行跳躍式比較
            while (j-increment>=0 && [array[j] integerValue]<[array[j-increment] integerValue]) {
                [array exchangeObjectAtIndex:j withObjectAtIndex:j-increment];
                j-=increment;
            }
        }
    }
}

6.快速排序(穩(wěn)定: 否)

/**
 最理想情況算法時(shí)間復(fù)雜度O(nlogn)雄家，最壞O(n^2),平均O(nlogn)
平均空間復(fù)雜度：O(nlogn)       O(nlogn)~O(n^2)
 */
- (void)quickSortArray:(NSMutableArray *)array withLeftIndex:(NSInteger)leftIndex andRightIndex:(NSInteger)rightIndex {
    if (leftIndex >= rightIndex) { // 如果數(shù)組長(zhǎng)度為0或1時(shí)返回
        return ;
    }
    
    NSInteger i = leftIndex;
    NSInteger j = rightIndex;
    NSInteger key = [array[i] integerValue]; // 記錄比較基準(zhǔn)數(shù)
    
    while (i < j) {
        /**** 首先從右邊j開(kāi)始查找比基準(zhǔn)數(shù)小的值 ***/
        while (i < j && [array[j] integerValue] >= key) { // 如果比基準(zhǔn)數(shù)大效诅，繼續(xù)查找
            j--;
        }
        // 如果比基準(zhǔn)數(shù)小，則將查找到的小值調(diào)換到i的位置
        array[i] = array[j];
        
        /**** 當(dāng)在右邊查找到一個(gè)比基準(zhǔn)數(shù)小的值時(shí)趟济，就從i開(kāi)始往后找比基準(zhǔn)數(shù)大的值 ***/
        while (i < j && [array[i] integerValue] <= key) { // 如果比基準(zhǔn)數(shù)小乱投，繼續(xù)查找
            i++;
        }
        // 如果比基準(zhǔn)數(shù)大，則將查找到的大值調(diào)換到j(luò)的位置
        array[j] = array[i];
        
    }
    
    // 將基準(zhǔn)數(shù)放到正確位置
    array[i] = @(key);
    
    /**** 遞歸排序 ***/
    // 排序基準(zhǔn)數(shù)左邊的
    [self quickSortArray:array withLeftIndex:leftIndex andRightIndex:i - 1];
    // 排序基準(zhǔn)數(shù)右邊的
    [self quickSortArray:array withLeftIndex:i + 1 andRightIndex:rightIndex];
}

7.堆排序

堆
堆（英語(yǔ)：heap)是計(jì)算機(jī)科學(xué)中一類特殊的數(shù)據(jù)結(jié)構(gòu)的統(tǒng)稱
堆總是滿足下列性質(zhì)：1. 堆中某個(gè)節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值顷编；2. 堆總是一棵完全二叉樹(shù)
將根節(jié)點(diǎn)最大的堆叫做最大堆或大根堆戚炫，根節(jié)點(diǎn)最小的堆叫做最小堆或小根堆

完全二叉樹(shù)
若設(shè)二叉樹(shù)的深度為h，除第 h 層外媳纬，其它各層 (1～h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)双肤，第 h 層所有的結(jié)點(diǎn)都連續(xù)集中在最左邊，這就是完全二叉樹(shù)钮惠。

/**
 時(shí)間復(fù)雜度為O(nlogn)
 */
- (void)heapSortArray:(NSMutableArray *)heapList len:(NSInteger)len {
    // 建立堆杨伙，從最底層的父節(jié)點(diǎn)開(kāi)始
    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.歸并排序(穩(wěn)定: 是)

歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并萌腿，得到完全有序的序列限匣；即先使每個(gè)子序列有序，再使子序列段間有序毁菱。若將兩個(gè)有序表合并成一個(gè)有序表米死，稱為二路歸并。

/**
 時(shí)間復(fù)雜度:
最優(yōu)時(shí)間: O(nlog(n))
最壞時(shí)間: O(nlog(n))
平均時(shí)間: O(nlog(n))
（1）“分解”——將序列每次折半劃分
（2）“合并”——將劃分后的序列段兩兩合并后排序
 */
- (NSArray *)mergeSortArray:(NSMutableArray *)array {
    // 排序數(shù)組
    NSMutableArray *tempArray = [NSMutableArray arrayWithCapacity:1];
    // 第一趟排序是的子數(shù)組個(gè)數(shù)為ascendingArr.count
    for (NSNumber *num in array) {
        NSMutableArray *subArray = [NSMutableArray array];
        [subArray addObject:num];
        [tempArray addObject:subArray];
    }
    /**
     分解操作 每一次歸并操作
     當(dāng)數(shù)組個(gè)數(shù)為偶數(shù)時(shí)tempArray.count/2; 當(dāng)數(shù)組個(gè)數(shù)為奇數(shù)時(shí)tempArray.count/2+1; 當(dāng)tempArray.count == 1時(shí)贮庞，歸并排序完成
     */
    while (tempArray.count != 1) {
        NSInteger i = 0;
        
        // 當(dāng)數(shù)組個(gè)數(shù)為偶數(shù)時(shí) 進(jìn)行合并操作峦筒， 當(dāng)數(shù)組個(gè)數(shù)為奇數(shù)時(shí)，最后一位輪空
        while (i < tempArray.count - 1) {
            
            // 將i 與i+1 進(jìn)行合并操作 將合并結(jié)果放入i位置上 將i+1位置上的元素刪除
            tempArray[i] = [self mergeArrayFirstList:tempArray[i] secondList:tempArray[i + 1]];
            [tempArray removeObjectAtIndex:i + 1];
            
            // i++ 繼續(xù)下一循環(huán)的合并操作
            i++;
        }
    }


    return tempArray.copy;
}
// 合并
- (NSArray *)mergeArrayFirstList:(NSArray *)array1 secondList:(NSArray *)array2 {
    
    // 合并序列數(shù)組
    NSMutableArray *resultArray = [NSMutableArray array];
    
    // firstIndex是第一段序列的下標(biāo) secondIndex是第二段序列的下標(biāo)
    NSInteger firstIndex = 0, secondIndex = 0;
    
    // 掃描第一段和第二段序列窗慎，直到有一個(gè)掃描結(jié)束
    while (firstIndex < array1.count && secondIndex < array2.count) {
        // 判斷第一段和第二段取出的數(shù)哪個(gè)更小物喷，將其存入合并序列卤材，并繼續(xù)向下掃描
        if ([array1[firstIndex] floatValue] < [array2[secondIndex] floatValue]) {
            [resultArray addObject:array1[firstIndex]];
            firstIndex++;
        } else {
            [resultArray addObject:array2[secondIndex]];
            secondIndex++;
        }
    }
    // 若第一段序列還沒(méi)掃描完，將其全部復(fù)制到合并序列
    while (firstIndex < array1.count) {
        [resultArray addObject:array1[firstIndex]];
        firstIndex++;
    }
    // 若第二段序列還沒(méi)掃描完峦失，將其全部復(fù)制到合并序列
    while (secondIndex < array2.count) {
        [resultArray addObject:array2[secondIndex]];
        secondIndex++;
    }
    // 返回合并序列數(shù)組
    return resultArray.copy;
}

9.二分查找

/**
 二分查找法只適用于已經(jīng)排好序的查找
 */
- (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.遞歸

斐波那契數(shù)列問(wèn)題
- (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)];//遞歸公式
}