1 快速排序：
每次排序：快速排序的一次划分算法从两头交替搜索，直到low和hight重合，因此其时间复杂度是O(n)；而整个快速排序算法的时间复杂度与划分的趟数有关
理想的情况是：每次划分所选择的中间数恰好将当前序列几乎等分，经过log2n趟划分，便可得到长度为1的子表。这样，整个算法的时间复杂度为O(nlog2n)
最差最坏的情况是：每次所选的中间数是当前序列中的最大或最小元素，这使得每次划分所得的子表中一个为空表，另一子表的长度为原表的长度-1。这样，长度为n的数据表的快速排序需要经过n趟划分，使得整个排序算法的时间复杂度为O(n2)。

平均复杂度o(nlog(n))

空间复杂度
最优o(log(n)) 最差 o（n）

void quick_sort(vector<int> &nums, int l, int r){
    if(l >= r) return;
    int x = nums[l + r >> 1];
    int i = l - 1, j = r + 1;
    while(i < j){
        do ++i; while(nums[i] < x);
        do --j; while(nums[j] > x);
        if(i < j) swap(nums[i], nums[j]);
    }

    quick_sort(nums, l, j);
    quick_sort(nums, j + 1, r);
}

2 插入排序
插入排序的平均时间复杂度也是 O(n^2)，空间复杂度为常数阶 O(1)，具体时间复杂度和数组的有序性也是有关联的。
插入排序中，当待排序数组是有序时，是最优的情况，只需当前数跟前一个数比较一下就可以了，这时一共需要比较 N-1 次，时间复杂度为 O(N)。
最坏的情况是待排序数组是逆序的，此时需要比较次数最多，最坏的情况是 O(n^2)
https://www.runoob.com/data-structures/insertion-sort.html

void insert_sort(vector<int> &nums){
    int n = nums.size();
    for(int i = 1; i < n; ++i){
        int j = i - 1, k = i;
        while(j >= 0 && nums[k] < nums[j]){
            swap(nums[k--], nums[j--]);
        }
    }
}

3 冒泡排序
每次遍历空间将 未排序的最大值 放到随后的位置。
平均时间 o(n^2)
https://www.runoob.com/python3/python-bubble-sort.html

void bubble_sort(vector<int> &nums){
    int n = nums.size();
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n - i - 1; ++j){
            if(nums[j] > nums[j + 1]) swap(nums[j], nums[j + 1]);
        }
    }
}

4 选择排序
无论什么情况都是o（n^2）
每次遍历找到最大值 或者 最小值

void select_sort(vector<int> &nums){
    int n = nums.size();
    int index_min = 0;
    for(int i = 0; i < n; ++i){
        for(int j = i + 1; j < n; ++j){
            index_min = i;
            if(nums[index_min] > nums[j]) index_min = j;
        }
        swap(nums[index_min], nums[i]);
    }
}

5 归并排序
时间复杂度 o(nlog(n))
空间复杂度 o(n)

void merge_sort(vector<int> &nums, int l, int r){
//1 找到中点位置
//2 递归
//3 合并两个序列
    if(l >= r) return;
    int mid = l + r >> 1;

    merge_sort(nums, l, mid);
    merge_sort(nums, mid + 1, r);

    vector<int> res(r - l + 1, 0);
    int i = l, j = mid + 1, k = 0;
    while(i <= mid && j <= r){
        if(nums[i] <= nums[j]) res[k++] = nums[i++];
        else res[k++] = nums[j++];
    }
    while(i <= mid) res[k++] = nums[i++];
    while(j <= r) res[k++] = nums[j++];
    k = 0;
    for(int i = l; i <= r; ++i){
        nums[i] = res[k++];
    }
}