X

曜彤.手记

随记,关于互联网技术、产品与创业

  1. 二分查找
  2. 选择排序
  3. 快速排序
  4. 散列表
  5. 广度优先搜索(BFS)
  6. Dijkstra 算法

基本算法概括(随记)

总结一波常用的基本算法,基于 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 算法

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




评论 | Comments


Loading ...