「数据结构」八大排序(超详解 附动图 源码)(3)

代码如下：
// 插入排序void InsertSort(int* a, int n){ assert(a); int i = 0; for (i = 0; i < n - 1; i )//因为x元素位置是i的下一个位置，为防止x越界，需要使 i < n-1 { int end = i;//已经有序的最后一个元素(一个元素不需要排序，所以默认从0开始) int x = a[end 1];//需要排序的元素 //单趟 while (end >= 0) { //若前一个数字小于x，则需将他向右移动 if (a[end] > x) { a[end 1] = a[end]; //继续判断前面的元素 --end; } //前面元素小于x else { break; } } //将x插入正确位置(两种情况) //1.前面的数字小于x //2.前面的数字都大于x，x放在下标为0处 a[end 1] = x; }}
直接插入排序的特性总结：
元素集合越接近有序，直接插入排序算法的时间效率越高 时间复杂度：O(N^2) 空间复杂度：O(1)，它是一种稳定的排序算法 稳定性：稳定

2.希尔排序

希尔排序法又称缩小增量法。
基本思想：
先选定一个整数gap，把待排序文件中所有记录分成gap个组，所有距离为gap的记录分在同一组内，并对每一组内的元素进行排序。
然后将gap逐渐减小重复上述分组和排序的工作。
当到达gap=1时，所有元素在统一组内排好序。
静态图演示：

动图演示：
这里重要的是理解分组思想，每一个组其实就是一个插入排序，相当于进行多次插入排序。