总结一波常用的基本算法，基于 C++ 描述。本文内容将持续更新。

二分查找

可用于对有序数组进行排序，时间复杂度 O(logn)；

#include <iostream> 
using namespace std; 
  
int binarySearch(int arr[], int l, int r, int x) {
  // the search boundary;
  if (r >= l) { 
    int mid = l + (r - l) / 2; 
    if (arr[mid] == x)
      return mid; 
    if (arr[mid] > x)
      return binarySearch(arr, l, mid - 1, x); 
    return binarySearch(arr, mid + 1, r, x); 
  } 
  return -1;
}

选择排序

可用于对数组进行排序，如倒序时每次遍历剩余元素寻找目标最小值，然后按顺序与已排好部分后面的元素进行交换。时间复杂度 O(n2)；

#include <array>

void selectionSort(int arr[], int n) { 
    int i, j, min_idx; 

    for (i = 0; i < n - 1; i++) { 
        min_idx = i; 
        for (j = i + 1; j < n; j++) {
      if (arr[j] < arr[min_idx]) 
        min_idx = j; 
    }

        std::swap(arr[min_idx], arr[i]); 
    } 
} 

快速排序

分治法。时间复杂度平均 O(nlogn)，最坏 O(n2)；

template <typename T>
void quick_sort_recursive(T arr[], int start, int end) {
  if (start >= end)
    return;
  T mid = arr[end];

  int left = start, right = end - 1;
  while (left < right) {
    while (arr[left] < mid && left < right)
      left++;
    while (arr[right] >= mid && left < right)
      right--;
    std::swap(arr[left], arr[right]);
  }

  if (arr[left] >= arr[end])
    std::swap(arr[left], arr[end]);
  else
    left++;

  quick_sort_recursive(arr, start, left - 1);
  quick_sort_recursive(arr, left + 1, end);
}
template <typename T>
void quick_sort(T arr[], int len) {
  quick_sort_recursive(arr, 0, len - 1);
}

散列表

基于“散列函数”实现，算法时间复杂度 O(1)。

• 冲突：如果两个键映射到了同一个位置，就在这个位置存储一个链表；
• 填装因子：散列表包含的元素数 / 位置总数；一旦填装因子大于0.7，就需要调整散列表的长度；

广度优先搜索（BFS）

适用于无权重图的最短路径搜索过程，可基于队列实现。

Dijkstra 算法

适用于非负权重图的最短路径搜索过程。