一文看懂直接插入排序和希尔排序

要说排序算法里面比较简单的，我觉得直接插入排序算是一个。
直接插入排序的原理很简单，就是把一个数字插入到一个有序的数组中。
比如有这么一个数组：
1，3，5，7然后要把 4 插进去。
过程不难，4跟 7 比，7大，把 7 往后移动；
4跟 5 比，5大，把 5 往后移动；
4跟 3 比，3小，于是直接把4放到第三个位置上。
但是问题又来了，去哪找一个有序的数组，排序本来就是没有顺序的。
于是就有了一个理论，如果一个数组中只有一个元素，那么它一定是有序的。
比如有这么一个数组：6 4 5 3 7先把 6 当作一个单独的数组，那么它一定是有序的。
把 4 插入到这个有序的数组中，先把 4 记下来，4跟 6 比，6向后移动，然后把 4 放到第一个位置。4 6 5 3 7接下来再把 5 插入到4 6这个有序的数组中，过程一样。 4 5 6 3 7循环下去，最终一定会得到一个有序的数组。
代码也不难。#include #include #include #define size 100000void insert_sort(int *a, int size){ int i, j, num; for (i = 1; i = 0; j--) { if (num < a[j]) { a[j + 1] = a[j]; } else { break; } } a[j + 1] = num; }}int main(){ int num, arr[size] = {0}, i; //随机产生数组 srand(time(null)); for (i = 0; i < size; i++) { arr[i] = rand() % 100; } insert_sort(arr, size); for (i = 0; i 0; h /= 2) { for (i = h; i = 0; j = j - h) { if (num < a[j]) { a[j + h] = a[j]; } else { break; } } a[j + h] = num; } }}int main(){ int num, arr[size] = {0}, i; //随机产生数组 srand(time(null)); for (i = 0; i < size; i++) { arr[i] = rand() % 100; } shell_sort(arr, size); for (i = 0; i < size; i++) { printf(%d , arr[i]); } printf(); return 0;}最后来试下 5 万个数据排序，两者的差距肉眼可见。root@turbo:test# time ./insert_sort real 0m1.740suser 0m1.724ssys 0m0.000sroot@turbo:test# time ./shell_sort real 0m0.008suser 0m0.004ssys 0m0.004sroot@turbo:test#