插入排序分为直接插入排序和希尔排序，希尔排序是在直接插入排序的基础上做出的优化版本(原因后面解释)。

代码如下:

//直接插入排序
void InsertSort(int arr[], int sz)
{for (int i = 0; i < sz - 1; i++){int mark = i;int tmp = arr[mark + 1];while (mark >= 0){if (tmp < arr[mark]){arr[mark + 1] = arr[mark--];}else{break;}arr[mark + 1] = tmp;}}
}
//希尔排序
void ShellSort(int arr[], int sz)
{int gap = sz;while (gap > 1){gap = gap / 3 + 1;for (int i = 0; i < sz - gap; i++){int mark = i;int tmp = arr[mark + gap];while (mark >= 0){if (tmp < arr[mark]){arr[mark + gap] = arr[mark];mark -= gap;}else{break;}arr[mark + gap] = tmp;}}}
}
//打印数组
void Print(int arr[], int sz)
{for (int i = 0; i < sz; i++){printf("%d ", arr[i]);}printf("\n");
}

头文件：

#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
void InsertSort(int arr[], int sz);
void ShellSort(int arr[], int sz);
void Print(int arr[], int sz);

测试:

因为直接插入排序时间复杂度最好是O(n),最坏是O(n^2），最坏情况是排序对象是降序排列的，希尔通过把排列对象划分成若干部分，这些部分内部进行直接插入排序，粗略把排序对象排列成升序，从而优化排序过程，也即是希尔把直接插入排序的最坏情况避免了。

谢谢观看!