二分查找

最简单的算法，直接无脑默写就完事了

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while ( left <= right ) {
            int mid = (left + right) / 2;
          	// if 判断的顺序，应该先判断是否相等
            if ( nums[mid] == target ) return mid;
            else if ( nums[mid] > target ) right = mid - 1;
            else left = mid + 1;
        }
        return -1;
    }
};

二路归并

在之前的博文中有写过归并排序，点击跳转

快速排序

这里的代码来源于LeetCode，多了更多细节上的处理，否则无法通过 LeetCode 的测试

class Solution {
public:
    // quickSort
    vector<int> sortArray(vector<int>& nums) {
        quickSort(nums, 0, nums.size()-1);
        return nums;
    }
    int partation(vector<int>& arr, int left, int right) {
        int random = left + rand() % (right - left + 1);
        swap(arr[random], arr[left]);
        int pivot = arr[left];
        while ( left < right ) {
            while ( left < right && arr[right] >= pivot ) {
                right--;
            }
            arr[left] = arr[right];
            while ( left < right && arr[left] <= pivot ) {
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = pivot;
        return left;
    }
    void quickSort(vector<int>& arr, int left, int right) {
        if ( arr.size() < 2 || left >= right ) return;
      	// 主要增加的细节处理在下面这部分的函数中
        int p = partation(arr, left, right);
        quickSort(arr, left, p-1);
        quickSort(arr, p+1, right);
    }
};

堆排序

应用场景

当有大量的元素需要排序（比如有十万个元素），取出 topX 的元素时，如果使用其他排序，将整个无序序列排序成为有序序列，会消耗大量的计算资源，但实际上我们需要的只是 X 个元素。堆排序使用的是堆这种数据结构设计的选择排序算法，是一种不稳定的排序方法，时间复杂度为 O(nlogn)。

基本思路

1. build an unorder array into a head
2. swap(top element in heap, end element in heap)
3. readjust the heap structure, repeat step1 and step2 util the array is ordered

pseudocode

// build big top heap
loop i = arr.length/2-1; i >= 0; i--
  adjustHead()
end loop
  
 // adjust the heap structure
 loop i = arr.length-1; i >= 0; i--
   swap(arr[0], arr[i])
   adjustHeap()
 end loop

代码

来源见注释

#include<iostream>
#include<algorithm>
using namespace std;

// 代码作者：机智翔学长（B站，CSDN同名）
// 赠送内容，堆排序，从小到大排序，故大顶堆获取数据后放在末尾

// 从下标l往下调整到r
void adjustHeap(int a[], int l, int r){
    if(l>=r){
        return ;
    }
    int i = l;
    int j = 2*i+1;
    while(j<=r){
        if(j+1<=r && a[j+1]>a[j]){
            // i节点下的两个子节点j和j+1(如果存在),选择大的那个和i节点比较
            j = j+1;
        }
        if(a[j]>a[i]){
            // 如果子节点j大于父节点i，则交换
            swap(a[i], a[j]);
        }else{
            break;
        }
        i = j;
        j = 2*i+1;
    }
}

// debug
void debugOut(int a[], int l, int r){
    cout << "\ndebug out:" << endl;
    for(int i=l;i<=r;i++){
        cout << a[i] << " ";
    }
    cout << endl;
}

// 堆排序，数组a[]，下标为l~r (实际上l为0)
void heapSort(int a[], int l, int r){

    // 先构建一个大顶堆
    for(int i=(r-1)/2;i>=l;i--){
        // i从最后一个父节点开始，往上
        adjustHeap(a, i, r); // 将数组a[]从i到r进行调整
    }

    // 再取出堆顶元素放在数组后边，重新调整堆
    for(int j=r;j>=l;j--){
        swap(a[l], a[j]);
        debugOut(a, l, r); // debug 可删
        adjustHeap(a, l, j-1);
    }
}

int main(){
    int a[] = {4, 6, 8, 5, 9};
    int len = sizeof(a)/sizeof(int);
    heapSort(a, 0, len-1);
    cout << "\n\nafter sort:" << endl;
    for(int i=0;i<len;i++){
        cout << a[i] << " ";
    }
}

Dijkstra

源代码

#include<bits/stdc++.h>

static int INF = INT_MAX;

/**
 * 
 * @param n 节点个数
 * @param src 起点
 * @param w[][] 邻接矩阵
 * @param vis[] 是否被访问过
 * @param dist[] 从src到n的最短路径
 */
void Dijkstra(int n, int src, vector<vector<int>> &w, vector<bool> &vis, vector<int> &dist) {
    // 初始化
    // 全部设置为未访问过
    fill(vis.begin(), vis.end(), false);
    fill(dist.begin(), dist.end(), INF);
    dist[src] = 0;

    for (int i = 0; i < n; ++i) {
        // 在未访问过的节点中选择路径最短的一个
        int min_index = -1;
        int MIN = INF;
        for (int j = 0; j < n; ++j) {
            if (!vis[j] && dist[j] < MIN) {
                min_index = j;
                MIN = dist[j];
            }
        }
        // 没有找到最小 return
        if (min_index == -1) return;
        // 找到最小，设置为已被访问
        vis[min_index] = true;
        // 更新 从src 经过 上一步选择出的最小的节点 到达 dist[v] 的距离
        for (int v = 0; v < n; ++v) {
            // 未被访问 && 可到达 && 路径更短
            // 经过 min_index ，从 src 到 v 的路径更短 -> 更新
            if (!vis[v] && w[min_index][v] != INF && dist[min_index] + w[min_index][v] < dist[v]) {
                // 更新路径
                dist[v] = dist[min_index] + w[min_index][v];
            }
        }
    }
    // 打印结果
    cout << "dist[]: ";
    for (int i: dist) {
        cout << i << " ";
    }
    cout << endl;
}

int main() {
    int n = 5;
    vector<vector<int>> w = {
            {0,   10,  3,   INF, INF},
            {INF, 0,   1,   2,   INF},
            {INF, 4,   0,   8,   2},
            {INF, INF, INF, 0,   7,},
            {INF, INF, INF, 9,   0,}
    };
    // 是否被访问过
    vector<bool> vis(n);
    vector<int> dist(n);

    Dijkstra(n, 0, w, vis, dist);

    return 0;
}

运行结果