我的Github地址 : Jerry4me, demo : JRBaseAlgorithm

本文主要是通過通俗易懂的算法和自然語言, 向大家介紹基礎的計算機排序算法和查找算法, 還有一些作為一名程序猿應該知道的名詞, 數(shù)據(jù)結構, 算法等等. 但是僅僅止于介紹, 因為本人能力不足, 對一些高級的算法和數(shù)據(jù)結構理解不夠通透, 所以也不作太多的深入的剖析.. demo都在我的Github中能找得到.

同樣的, 通過最近面試實習生的機會, 把一些基礎都撿起來, 鞏固鞏固, 同時如果能幫助到大家, 那也是極好的. 廢話不多說, 入正題吧.

排序算法

ps : 基數(shù)排序的復雜度中, r代表關鍵字的基數(shù), d代表位數(shù), n代表關鍵字的個數(shù). 也就是說, 基數(shù)排序不受待排序列規(guī)模的影響.

算法復雜度 : 這里表中指的是算法的時間復雜度, 一般由O(1), O(n), O(logn), O(nlogn), O(n2), ..., O(n!). 從左到右復雜度依次增大, 時間復雜度是指在多少時間內能夠執(zhí)行完這個算法, 常數(shù)時間內呢, 還是平方時間還是指數(shù)時間等等.
還有個概念叫空間復雜度, 這就指的是執(zhí)行這個算法需要多少額外的空間. (源數(shù)組/鏈表所占的空間不算)

穩(wěn)定性 : 算法的穩(wěn)定性體現(xiàn)在執(zhí)行算法之前, 若a = b, a在b的前面, 若算法執(zhí)行完之后a依然在b的前面, 則這個算法是穩(wěn)定的, 否則這個算法不穩(wěn)定.

選擇排序

原理 : 每次從無序區(qū)中找出最小的元素, 跟無序區(qū)的第一個元素交換

void selectSort(int array[], int count){
    for (int i = 0; i < count; i++) {
        // 最小元素的位置
        int index = i;
        // 找出最小的元素所在的位置
        for (int j = i + 1; j < count; j++) {
            if (array[j] < array[index]){
                index = j;
            }
        }
        // 交換元素
        int temp = array[index];
        array[index] = array[i];
        array[i] = temp;
    }
}

冒泡排序

原理 : 每次對比相鄰兩項的元素的大小, 不符合順序則交換

void bubblingSort(int array[], int count){
    for (int i = 0; i < count; i++) {
        // 交換相鄰的元素
        for (int j = 1; j < count - i; j++) {
            if (array[j] < array[j-1]) {
                // 交換元素
                int temp = array[j-1];
                array[j-1] = array[j];
                array[j] = temp;
            }
        }
    }
}

插入排序

原理 : 每次將一個待排序的記錄，按其關鍵字大小插入到前面已經排好序的子序列中的適當位置，直到全部記錄插入完成為止。

void insertSort(int array[], int count) {
    int i, j, k;
    
    for (i = 1; i < count ; i++) {
        for (j = i - 1; j >= 0; j--) { // 為a[i]在a[0, i-1]上找一個合適的位置
            if(array[j] < array[i]) break;
        }
        
        if (j != i-1) { // 找到了一個合適的位置j
            int temp = array[i];
            // 將比array[i]大的數(shù)據(jù)全部往后移
            for(k = i - 1; k > j; k--) {
                array[k+1] = array[k];
            }
            // 將array[i]放入合適的位置
            array[k+1] = temp;
        }
    }
}    

希爾排序

其實就是分組插入排序, 也稱為縮小增量排序. 比普通的插入排序擁有更高的性能.

算法思想 : 根據(jù)增量dk將整個序列分割成若干個子序列. 如dk = 3, 序列1, 7, 12, 5, 13, 22 就被分割成1, 5, 7, 13和12, 22, 在這幾個子序列中分別進行直接插入排序, 然后依次縮減增量dk再進行排序, 直到序列中的元素基本有序時, 再對全體元素進行一次直接插入排序. (直接插入排序在元素基本有序的情況下效率很高)

void shellSort(int array[], int count){
    for (int dk = count / 2; dk > 0; dk = dk / 2) { // dk增量
        for (int i = 0; i < dk; i++) { // 直接插入排序
            for (int j = i + dk; j < count; j += dk) {
                if (array[j] < array[j - dk]) { // 如果相鄰的兩個元素, 后者比前者大, 則不用調整
                        int temp = array[j];
                        int k = j - dk;
                        while (k >= 0 && array[k] > temp) { // 每次while循環(huán)結束后, 保證把最小的插入到每組的最前面
                            array[k + dk] = array[k];
                            k -= dk;
                        }
                        // 每組第一個元素為最小的元素
                        array[k + dk] = temp;
                }
            }
        }
    }
}

歸并排序

原理 : 歸并排序是把序列遞歸地分成短序列，遞歸出口是短序列只有1個元素(認為直接有序)或者2個序列(1次比較和交換),然后把各個有序的段序列并成一個有序的長序列，不斷合并直到原序列全部排好序。

void merge(int array[], int temp[], int start, int middle, int end) {
    // 將兩個有序序列array[start, middle]和array[middle+1, end]進行合并    
    int i = start, m = middle, j = middle + 1, n = end, k = 0;
    while(i <= m && j <= n) { // 哪個小就先插那個, 然后把temp下標和array插入位置的下標++
        if (array[i] <= array[j]) {
            temp[k++] = array[i++];
        } else {
            temp[k++] = array[j++];
        }
    }
    // 插完之后看誰沒插完就繼續(xù)插誰
    while(i <= m) temp[k++] = array[i++];
    while(j <= n) temp[k++] = array[j++];
    // 把temp的元素copy回array中
    for (int i = 0; i < k; i++) array[start + i] = temp[i];
}

void mSort(int array[], int temp[], int start, int end) {
    if (start < end) {
        int middle = (start + end) / 2;
        mSort(array, temp, start, middle); // 遞歸出來以后左邊有序
        mSort(array, temp, middle + 1, end); // 右邊有序
        merge(array, temp, start, middle, end); // 合并兩個有序序列
    }        
}

void mergeSort(int array[], int count){
    // 定義輔助數(shù)組
    int *temp = (int *)malloc(sizeof(array[0]) * count);
    // 開始進行歸并排序
    mSort(array, temp, 0, count - 1);
    // 釋放指針
    free(temp);
}

堆排序

• 二叉堆的定義

  • 二叉堆是完全二叉樹或者是近似完全二叉樹。

• 二叉堆滿足二個特性：

  • 父結點的鍵值總是大于或等于（小于或等于）任何一個子節(jié)點的鍵值。
  • 每個結點的左子樹和右子樹都是一個二叉堆（都是最大堆或最小堆）。

大頂堆 : 父結點的鍵值總是大于或等于任何一個子節(jié)點的鍵值
小頂堆 : 父結點的鍵值總是小于或等于任何一個子節(jié)點的鍵值

算法思想 : 堆排序 = 構造堆 + 交換堆末尾元素與根結點 + 刪除末尾結點 + 構造堆 + 交換....依次循環(huán), 由于根結點必定是堆中最大(最小)的元素, 所以刪除出來的元素序列也必定是升序(降序)的.

void minHeapFixdown(int array[], int i, int count) {

    int j, temp;

    temp = array[i];
    j = 2 * i + 1;
    while(j < count) {
        if (j + 1 < count && array[j+1] < array[j]) j++; // 找出較小的子節(jié)點
    
        if (array[j] >= temp) break; // 如果較小的子節(jié)點比父節(jié)點大, 直接返回
    
        array[i] = array[j]; // 設置父節(jié)點為較小節(jié)點
        i = j; // 調整的子節(jié)點作為新一輪的父節(jié)點
        j = 2 * i + 1; // 調整的子節(jié)點的子節(jié)點
    }

    array[i] = temp;
}

void heapSort(int array[], int count) {

    for (int i = (count - 1) / 2; i >= 0; i--) {
        // 構造小頂堆
        minHeapFixdown(array, i, count);
    }

    for (int i = count - 1; i >= 1; i--) {
    
        // 交換根結點與最末節(jié)點
        int temp = array[i];
        array[i] = array[0];
        array[0] = temp;
    
        // 剩余的n-1個元素再次建立小頂堆
        minHeapFixdown(array, 0, i);
    
    }

}

快速排序

算法思想 : 先從數(shù)列中取出一個數(shù)作為基準數(shù) -> 將比這個數(shù)大的數(shù)全放到它的右邊，小于或等于它的數(shù)全放到它的左邊 -> 再對左右區(qū)間重復第二步，直到各區(qū)間只有一個數(shù)

int quickSortPartition(int array[], int start, int end) {

    int i = start, j = end;
    // 默認第一個元素為哨兵
    int sentry = array[i];

    while (i < j) {
    
        // 從右往左找第一個小于哨兵的元素
        while (i < j && array[j] >= sentry) j--;
        // 找到了
        if (i < j) {
            array[i] = array[j];
            i++;
        }
    
        // 從左往右找第一個大于哨兵的元素
        while(i < j && array[i] <= sentry) i++;
        // 找到了
        if (i < j) {
            array[j] = array[i];
            j--;
        }
        
    }
    // 把哨兵放到i == j的位置上
    array[i] = sentry;

    // 返回哨兵的位置
    return i;
}

void quickSort(int array[], int start, int end) {

    if (start < end) {
    
        // 找出分界點
        int index = quickSortPartition(array, start, end);
        quickSort(array, start, index - 1); // 對分界點左邊進行排序
        quickSort(array, index + 1, end); // 對分界點右邊進行排序
    }

}

void quickSortEntry(int array[], int count) {
    quickSort(array, 0, count - 1);
}

基數(shù)排序

基數(shù)排序的算法復雜度不會因為待排序列的規(guī)模而改變. 基數(shù)排序又稱為桶排序. 基數(shù)排序有3個重要概念 :

• r : 關鍵字的基數(shù), 指的是關鍵字k的取值范圍, 十進制數(shù)的話, k=10
• d : 位數(shù)
• n : 關鍵字的個數(shù)

這里給個例子, 沒有代碼.

例如一組序列121 83 17 9 13

1. 先根據(jù)個位數(shù)排序
    121 83 13 17 9
2. 再根據(jù)十位數(shù)排序
    9 13 17 121 83
3. 再根據(jù)百位數(shù)排序
    9 13 17 83 121
4. 由于沒有千位數(shù), 所以算法結束

ps : 需要注意的是, 基數(shù)排序每一輪排序所采用的算法必須是穩(wěn)定的排序算法, 
也就是說, 例如13和17的十位數(shù)均為1, 但是由于個位數(shù)排序的時候13是在17的前面的, 
所以十位數(shù)排序過后13也必須在17的前面. 

查找算法

順序查找

算法思想 : 顧名思義就是從數(shù)組的0坐標開始逐個查找對比.

int orderSearch(int array[], int num, int count) {
    int index = -1;

    for (int i = 0; i < count; i++) {
        if (array[i] == num) {
            index = i;
            break;
        }
    }
    return index;
}

折半查找

算法思想 : 在一個有序數(shù)組里, 先對比數(shù)組中間的數(shù)middle與要查找的數(shù)num的大小關系
- middle == num : 直接返回
- middle < num : 遞歸查找數(shù)組右半部分
- middle > num : 遞歸查找數(shù)組左半部分

int binarySearch(int array[], int num, int start, int end) {

    int index = -1;

    if (start <= end) {

        int middle = (start + end) / 2; // 數(shù)組中點
        if (array[middle] == num) {
            index = middle; // 找到了
            return index;
        }
        else if (array[middle] > num) {
            return binarySearch(array, num, start, middle - 1); // 查找數(shù)組左邊
        } else if (array[middle] < num) {
            return binarySearch(array, num, middle + 1, end); // 查找數(shù)組右邊
        }
    
    }

    return index;
}

哈希查找

哈希查找需要一張哈希表, 哈希表又稱為散列法, 是高效實現(xiàn)字典的方法. 查找速度在O(1), 這說明無論你需要查找的數(shù)據(jù)量有多大, 他都能在常數(shù)時間內找到, 快得有點違背常理吧? 嘿嘿.

哈希表幾個重要的概念 :

• 負載因子 : α = n / m (n為鍵的個數(shù), m為單元格個數(shù)), 負載因子越大, 發(fā)生沖突的概率則越大
• 哈希函數(shù) :
  • 哈希函數(shù)是指你把一樣東西存進去之前, 先對它的key進行一次函數(shù)轉換, 然后在通過轉換出來的值作為key, 把你要存的東西存在表上.
• 碰撞解決機制 :

  • 如果兩樣東西通過哈希函數(shù)算出來的key相同怎么辦? 東西怎么存? 這個時候就是碰撞檢測機制派上用場的時候

  • 方法一 : 開散列法, 也稱分離鏈法 : 即相當于在數(shù)組中每個格子是一個鏈表, 只要發(fā)生沖突就把后來的value拼接在先來的value后面, 形成一條鏈.

  • 方法二 : 閉散列法, 也稱開式尋址法 :

    • 再哈希法 : 使用其他的哈希函數(shù)對key再次計算, 直到沒有發(fā)生沖突為止(計算量增加, 不推薦)
    • 線性勘測法 : 通過一個公式, 算出下一個地址, (存儲連續(xù)的)
    • 二次探測法 : 生成的地址不是連續(xù)的, 而是跳躍的.

可以這么說, 哈希函數(shù)設計得越好, 沖突越少, 哈希表的效率就越高.

需要了解的名詞

• 旅行商問題

  • 哈密頓回路 : 經過圖中所有頂點一次僅一次的通路

• 凸包問題

  • 凸集合 : 平面上一個點集合, 任意兩點為端點的線段都屬于該集合
  • 凸包 : 平面上n個點, 求包含這些點的最小凸多邊形
  • 極點 : 不是線段的中點

• 曼哈頓距離

  • dM (p1, p2) = |x1 - x2| + |y1-y2|

• 深度優(yōu)先查找(DFS) : 用棧實現(xiàn)

• 廣度優(yōu)先查找(BFS) : 用隊列實現(xiàn)

• 拓撲排序( 無環(huán)有向圖 )

  • 深度優(yōu)先查找 -> 記住頂點(出棧)的順序, 反過來就是一個解
  • 找源, 它是一個沒有輸入邊的頂點, 然后刪除它和它出發(fā)的所有邊, 重復操作直到沒有源為止.

• 2-3樹

  • 可以包含兩種類型的節(jié)點
    • 2節(jié)點 : 只包含1個鍵和2個子女
    • 3節(jié)點 : 包含2個鍵和3個子女
    • 高度平衡<所有葉子節(jié)點必須位于同一層>

• BST樹 :

  • 也稱為B樹
  • 二叉查找樹, 隨著插入和刪除的操作有可能不是平衡的.

• AVL樹 :

  • 平衡二叉查找樹
  • 左右子樹深度只差不超過1
  • 左右子樹仍為平衡二叉樹

• RBT紅黑樹 :

  • 一種平衡二叉樹
  • 跟AVL樹類似, 通過插入和刪除操作時通過特定操作保持二叉查找樹的平衡, 從而有較高的查找性能.
  • 相當于弱平衡的AVL數(shù)(犧牲了一定次數(shù)的旋轉操作), 若查找 > 插入/刪除, 則選擇AVL樹; 若差不多則選擇紅黑樹

• 哈夫曼樹

  • 葉子之間的加權路徑長度達到最小
  • 哈夫曼編碼
    • 自由前綴變長編碼

幾種圖論的算法

• Warshall算法

  • 求有向圖的傳遞閉包
  • 算法思想
    • 選取一個頂點作為橋梁, 考察所有頂點是否可以通過該橋梁到達其他的頂點

• Floyed算法

  • 求每個頂點到各個頂點的最短路徑
  • 算法思想
    • 選取一個頂點作為橋梁, 考察所有頂點是否可以通過該橋梁到達其他的頂點, 如果能, (如a到c, b為橋梁)再比較Dab + Dbc < Dac ? 如果成立, 則更新最短距離

• Prim算法

  • 求無向帶權連通圖的最小生成樹(每次按節(jié)點遞增)
  • 算法思想
    • 首先找出S = {你選取的一個頂點}, 然后添加另一頂點(該頂點∈(V-S)且它們兩頂點之間的邊的權重最小, 直到S = V.

• Kruskal算法

  • 求無向帶權連通圖的最小生成樹(每次按邊遞增)
  • 算法思想
    • 第一次選出權重最小的邊加入, 之后每次選擇權重最小的邊加入并不構成環(huán).

• Dijkstra算法

  • 求有向帶權圖中一個"源"到所有其他各頂點的最短路徑
  • 算法思想
    • 找一個源(起點), 之后求出離起點最近的點的距離; 然后第二近, 以此類推(允許通過其他點為中間點), 設置頂點集合S, 只要源到該頂點的距離已知就把該頂點加入到S中. 直到S包含了V中所有頂點.