面试-基本的算法要了如指掌，比如查找、排序、动态规划、分治等

在了解这些基本算法之前还是得先了解这些基本的数据结构，这些都是要熟记与心的。

基本数据结构

比如：字符串、链表、二叉树、堆、栈、队列、哈希等

字符串

string str = "hello world"; // 使用格式
// string 是类。
// str输出的大小，取决于size函数的返回值。

链表

class ListNode
{
 	public:
  	int val;
  	ListNode* next;
  	ListNode(int x): val(x), next(nullptr){}
}

class LinkedList
{
	private:
  	ListNode* head;
  public:
  	LinkedList():head(nullptr){}
  ...增删改查操作
}

二叉树

class TreeNode
{
	public:
  	int val;
  	TreeNode* left;
  	TreeNode* right;
  	TreeNode(int val): val(val), left(nullptr), right(nullptr){}
  	TreeNode(): val(0), left(nullptr), right(nullptr){}
}

class BinaryTree
{
	private:
  	TreeNode* root;
  public:
  	BinaryTree():root(nullptr){}
  ... 增删改查
}

堆

priority_queue<typename> pqu; // typename 可以表示为基本数据类型，或者是复杂的数据类型

基本算法分析-排序

选择排序

选择排序的算法流程如下：

1. 初始状态下，所有元素未排序，即未排序（索引）区间为[0, n-1]。
2. 选取区间[0, n-1]中的最小元素，将其与索引0处元素交换。完成后，数组前1个元素已排序。
3. 选取区间[1,n-1]中的最小元素，将其与索引1处元素交换。完成后，数组前2个元素已排序。
4. ....
5. 仅剩的一个元素必定是最大元素，无需排序，因此数组排序完成。

/* 选择排序 */
void selectionSort(vector<int> &nums) {
    int n = nums.size();
    // 外循环：未排序区间为 [i, n-1]
    for (int i = 0; i < n - 1; i++) {
        // 内循环：找到未排序区间内的最小元素
        int k = i;
        for (int j = i + 1; j < n; j++) {
            if (nums[j] < nums[k])
                k = j; // 记录最小元素的索引
        }
        // 将该最小元素与未排序区间的首个元素交换
        swap(nums[i], nums[k]);
    }
}

算法特性

事件复杂度：O(n)

空间复杂度：O(1)