起泡排序

https://www.bilibili.com/video/av49361421?p=75

初始版本时间复杂度O（n^2）。

改进：考虑到向量中的前段和后段是不是已经是有序的。前段有的话就不再继续排序，后段有的话就把hi点放到前段最大值那里。

算法是否稳定？

归并排序

https://www.bilibili.com/video/av18980253/

时间复杂度O（nlogn）。

先分，再merge归并。分而治之的算法。

C代码实现：

c
#include <stdio.h>
void merge_sort_recursive(int arr[], int reg[], int start, int end) {
    if (start >= end)
        return;
    int len = end - start, mid = (len >> 1) + start;
    int start1 = start, end1 = mid;
    int start2 = mid + 1, end2 = end;
    merge_sort_recursive(arr, reg, start1, end1);
    merge_sort_recursive(arr, reg, start2, end2);
    int k = start;
    while (start1 <= end1 && start2 <= end2)
        reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
    while (start1 <= end1)
        reg[k++] = arr[start1++];
    while (start2 <= end2)
        reg[k++] = arr[start2++];
    for (k = start; k <= end; k++)
        arr[k] = reg[k];
}
void merge_sort(int arr[], const int len) {
    int reg[len];
    merge_sort_recursive(arr, reg, 0, len - 1);
}
int main() {
    int a[]={1,2,3,3,2,4,5,6,7,8,3,4,5,6,22,33,44,22,11};
    int i= 19;
    merge_sort(a, i);
    while(i--)
        printf("%d    ",a[i]);
    return 0;
}