插入排序和希尔排序

1.直接插入排序

基本思想：
把待排序的数据按其大小逐个插入到一个已经排好序的有序序列中，直到所有的数据插入完成为止。

当插入第i个元素时，前面的a[0],a[1],...,a[i-1]个数据已经排好序了，此时用a[i]与a[i-1],a[i-2],...进行比较，找到插入位置就将a[i]插入，原来位置上的元素顺序后移

void InsertSort(int* a, int n)
{for (int i = 0; i < n-1; i++){int end = i;//记录已经有序的数据的最后一个数据的下标int tmp = a[end + 1];while (end >= 0){if (a[end] > tmp){a[end + 1] = a[end];end--;}else//a[end]<tmp，说明前（i+1）个数已经有序了{break;}}a[end + 1] = tmp;}
}

元素集合月接近有序，直接插入排序算法的时间效率更高
时间复杂度：O(N^2)
稳定性：稳定

2.希尔排序

希尔排序是直接插入排序的优化

1.预排序
2.直接插入排序
基本思想：
先选定一个整数，把待排序文件中所有数据分成gap个组，所有距离为gap的数据分在同一个组里，并对每一组的数据进行排序。然后，取gap=gap/3+1，重复上述分组的操作。当gap=1时，所有数据在同一组的已经排好序了

void ShellSort(int* a, int n)
{int gap = n;while(gap > 1){//+1保证最后一个gap一定是1//gap》1是预排序//gap==1是插入排序gap = gap / 3 + 1;for (int i = 0; i < n - gap; i++){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;}}
}

当gap>1时都是预排序，目的是让数组更接近有序。当gap==1时，数组已经接近有序了，这样就会很快
时间复杂度：O（N^1.3)（ps：时间复杂度是不固定的）
稳定性：不稳定