iOS 算法之排序、查找、遞歸

排序

冒泡排序（依次循環旁邊的比較放到後邊去）

/**
 最好時間複雜度是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^2)
 最壞時間複雜度是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;
            }
        }
    }
}

插入排序

- (void)insertSortArray:(NSMutableArray *)array {
    for (int i = 1; i < [array count]; i++) {
        int j = i;
        NSInteger temp = [[array objectAtIndex:i] integerValue];
        while (j > 0 && temp < [[array objectAtIndex:j - 1] integerValue]) {
            [array replaceObjectAtIndex:j withObject:[array objectAtIndex:(j - 1)]];
            j--;
        }
        [array replaceObjectAtIndex:j withObject:[NSNumber numberWithInteger:temp]];
    }
}

希爾排序

希爾排序是把記錄按下标的一定增量分組，對每組使用直接插入排序算法排序；随着增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至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;
            }
        }
    }
}

快速排序

/**
 最理想情況算法時間複雜度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];
}

堆排序

堆

堆（英語：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;
}

歸并排序

歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。将已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若将兩個有序表合并成一個有序表，稱為二路歸并。

/**
 時間複雜度為O(nlogn)
（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;
}

二分查找

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

遞歸

斐波那契數列問題

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

原文位址：

iOS 算法之排序、查找、遞歸

二分查找

遞歸

繼續閱讀

查找算法學習之二分查找（Python版本）——BinarySearch

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

Command Network(POJ 3164)---定根最小樹形圖模闆題題目描述輸入格式輸出格式輸入樣例輸出樣例分析源程式

開源低帶寬語音編解碼器

241 Different Ways to Add Parentheses（C代碼版）

【趨高機器視覺】機器視覺技術原了解析及解決方案

EGORefreshTableHeaderView 解讀代碼解讀 ELTableViewController 的使用寫在最後

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

今日頭條iOS用戶端啟動速度優化技術調研實測資料

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

筆試面試題目：滑動視窗(二)

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

hdu7108哈希