稳定排序（插入排序、冒泡排序、归并排序）

插入排序
我们可以从字面意思去理解这个排序方式，可以把序列前后分为两部分有序序列和待排序列，不断的在待排序列中取出一个数按某规则（从大到小或者从小到大）插入到有序序列中，直到待排序列都完成排序结束。
动图演示
可视化算法动图网站推荐：https://visualgo.net/en
PS：本图出处为此网站

C语言代码实现

void insert_sort(int *num, int n) {
    for (int i = 1; i < n; i++) {
        for (int j = i; j > 0 && num[j] < num[j - 1]; j--) {
            swap(num[j], num[j - 1]);
        }	
    }
    return ;
}

冒泡排序

动图演示

C语言代码实现

归并排序
归并这个词在中文的意思就是合并、并入的意思。而在数据结构中的定义是将两个或者两个以上的有序数列合成一个新的数列。该算法也是用的分治思想，把一个大问题分解成小问题，进行递归求解，有分而治之的意思。

动图演示

C语言代码实现

void merge_sort(int *num, int l, int r) {
    if (r - l <= 1) {
        if (r - l == 1 && num[r] < num[l]) {
            swap(num[l], num[r]);
        }
        return ;
    }
    int mid = (l + r) >> 1;
    merge_sort(num, l, mid);
    merge_sort(num, mid + 1, r);
    int *temp = (int *)malloc(sizeof(int) * (r - l + 1));
    int p1 = l, p2 = mid + 1, k = 0;
    while (p1 <= mid || p2 <= r) {
        if (p2 > r || (p1 <= mid && num[p1] <= num[p2])) {
            temp[k++] = num[p1++];
        } else {
            temp[k++] = num[p2++];
        }
    }
    memcpy(num + l, temp, sizeof(int) * (r - l + 1));
    free(temp);
    return ;
}

算法时间复杂度比较

排序算法	最好	平均时间	最坏	额外空间	复杂度
插入排序	O(n)	O(n2)	O(n2)	O(1)	简单
冒泡排序	O(n)	O(n2)	O(n2)	O(1)	简单
归并排序	O(N*log2N)	O(N*log2N)	O(N*log2N)	O(n)	复杂