1.直接插入排序
1.1基本思想：
1.假设一个数组中前n-1个数都有序了，将最后一个数插入到前面有序的数组中去，用待插入数与有序数组从后向前依次比较，直到找到比待插入数大（降序）或则小（升序）的数，将该数插到其后面；
2.一个无序的数组中，将第一个数看成有序的，将第二个数插入到前面，把前面两个变成有序；
3.再将第三个数插入到前面有序数组中，将前三个变成有序；
.......
将最后一个元素插入到前面的数组中去，整个数组就有序了；
图解：
代码实现：
//升序为例 void InsertSort(int a[],int n) { for (int i = 1; i < n - 1; i++) { int end = i; //将最后一个元素保存，避免当倒数第二个数比它大，往后移动时将它覆盖 int tmp = a[end]; while (end >= 0) { //从后向前比较，当比他大时，将该元素往后移动 if (a[end - 1] > tmp) { a[end] = a[end - 1]; } end--; //当找到比它小的数时，break跳出循环 if (a[end - 1] <= tmp) { break; } } //到这里有两种情况，1 end<0 退出循环 2 找到了比它小的数，break跳出循环 a[end] = tmp; } }
1.2性能分析
1.2.1时间复杂度：
最坏情况，逆序
时间复杂度为：1+2+3+4+……+n-1+n
时间复杂度为：O(N^2)
1.2.2空间复杂度：没有空间消耗
空间复杂度：O(1)
2.希尔排序
2.1基本思想：
先选定一个整数（记作gap）作为间距，把待排序的数据以gap间距分组，并对每一组的数据进行插入排序，然后再缩小间距（gap），当gap最后等于1时，所有数据就有序了；
希尔排序要先进行预排序，预排序完后再进行一次直接插入排序；
当gap>1时，就是预排序；
当gap=1时，就相当于直接插入排序；
预排序：
预排序是在选择排序的思想上，将一组数据以gap为数据间隔分组；如图
再将每一组数据进行直接选择排序；（如下图）
预排序的意义：是让大的数更快到后面去，小的数更快到前面去；如图：
预排序过后，在进行gap为1的直接插入排序之前，数组的数据已经很接近有序了，所以最后一次的直接插入排序在时间上有了优化；
代码实现：
void ShellSort(int* a, int n) { int gap = n; while (gap>1) { //当gap>1时，预排序，gap=1时，直接让数组有序； gap = gap / 3 +1; //一共分为了gap组，需要gap次的插入排序 for (int j = 0; j < gap; j++) { //一组数据的插入排序 for (int i = j; i < n - gap; i += gap) { int end = i; int tmp = a[end + gap]; while (end >= 0) { if (a[end] > tmp) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = tmp; } } } }
2.2性能分析
开始时，gap取值较大，子序列中的元素较少，排序速度快，克服了直接插入排序的缺点；
其次，gap值逐渐变小后，虽然子序列的元素逐渐变多，但大多元素已基本有序，能以近线性的速
度排好序；
2.2.1时间复杂度
根据复杂的数学计算，结论为：
时间复杂度为O(N^1.3)
2.2.2空间复杂度
除了两个数据交换时有空间消耗，就没有多余其他空间的消耗；
最好：有序 空间复杂度为0；
最坏：逆序 空间复杂度为O(N)；
平均空间复杂度为O(1)
