每次从待排序序列中取一个值，放到已排序好的序列中（放完后保证依旧有序）
时间复杂度：O（n^2）
空间复杂度：O（1）
稳定性：稳定
优点：空间复杂度低、实现简单、逻辑简单、n较小的情况下，n平方也不会很大，时间复杂度就不用考虑
直接插入排序有个特点：数据越有序，排序越快（时间复杂度越低）
代码实现：
//时间复杂度O（n^2） 空间复杂度O（1） 稳定性：稳定
//优点：实现简单 如果n小，n^2也就比较小 直接使用直接插入排序
//待排序数值tmp，待排序数值左侧就是有序数列，插入时分以下几种情况：
//1、待排序元素从右向左比较，找到中间某个值小于等于待排序元素（tmp），那就插入到这个值的j+1的位置
//2、待排序元素从右向左比较，找到第一个有序的元素值就比待排序元素（tmp）要小，那就直接不动
//3、待排序元素从右向左比较，直到找到最后一个有序元素值都比待排序元素值大，也就是触底了,j此时为-1，
// 那也就表示本次循环结束，最后我们让待排序元素插入到第一个元素j+1位置即可
void Intersect(int* arr, int len) {
for (int i = 1; i < len; i++) { //从第二个元素（待排序数值）开始，从右向左依次和已有序数值进行比较
int tmp = arr[i]; //待排序数值
int j; //j表示有序元素部分的下标
for (j = i - 1; j >= 0; j--) { //j从待排序数值的左边第一个数字开始，不断向前比较
if (tmp <= arr[j]) { //1、判断待排序数值是否小于等于已有序的部分数值
arr[j + 1] = arr[j]; //小于等于的话就让有序数列先统一向后挪，腾位置，等待往前插入
}
else { //2、待排序数值大于已有序的部分数值的话，就不动
break; //跳出循环，等待待排序元素原地插入（或者说不动）
// （或者说是插入到已有序数值的后面）
}
}
arr[j + 1] = tmp; //3、触底都没有找到比待排序元素小的值
//情况1：中间部分找到插入位置
//情况2：待排序元素位置不动
//情况3：循环结束都没有找到合适位置，那肯定是
// 要插入到首元素位置，此时j为-1
}
}
void Show(int* arr, int len) {
for (int i = 0; i < len; i++) {
printf("%3d", arr[i]);
}
printf("n");
}
int main() {
int arr[] = {10,4,7,1,16,3,8,13,12,22,11,21,5,9,19,6};
int len = sizeof(arr) / sizeof(arr[0]);
Intersect(arr, len);
Show(arr,len);
return 0;
}
二、希尔排序
希尔排序是对直接插入排序的优化
时间复杂度：O（n的1.5~1.7次方）
空间复杂度：O（1）
稳定性：不稳定
代码实现：
//时间复杂度O（1.5~1.7） 空间复杂度O（1） 稳定性：不稳定
void Shell_sort(int* arr, int len) {
int gap[] = { 5,3,1 }; //缩小增量数组
int len_gap = sizeof(gap) / sizeof(gap[0]); //长度是3
int z, i, j;
for (z = 0; z < len_gap; z++) { //整个arr数组一共要缩量循环3次
for (i = gap[z]; i < len; i++) { //每次缩量循环都是从gap[z]号下标开始，遍历整个数组arr
// z为0，gap[z]为5；z为1，gap[z]为3；z为2，gap[z]为1
int tmp = arr[i]; //待排序元素值
for (j = i - gap[z]; j >= 0; j = j - gap[z]) {
//此处循环是就是将gap[z]
if (tmp <= arr[j]) {
arr[j + gap[z]] = arr[j];
}
else{
break;
}
}
arr[j + gap[z]] = tmp;
}
}
}
void Show(int* arr, int len) {
for (int i = 0; i < len; i++) {
printf("%3d", arr[i]);
}
printf("n");
}
int main() {
int arr[] = {10,4,7,1,16,3,8,13,12,22,11,21,5,9,19,6};
int len = sizeof(arr) / sizeof(arr[0]);
Shell_sort(arr, len);
Show(arr,len);
return 0;
}
