版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/tianxiawushanu/article/details/142660275
1. 排序的概念及其应用
在正式讲解插入排序和希尔排序之前，我要带着大家理解我们为什么需要排序？以及排序在我们生活中有什么应用？学完这些之后，大家也许对排序算法就不会那么迷茫了。
1.1 排序的概念
排序：所谓排序，就是使一串记录，按照我们特定且可行的想法，递增或递减的排列起来的操作。
排序是一项操作！
1.2 排序的应用
看到这里，大家可以打开京东商城，当你想买一台新的手机时，却不知如何入手。你可能会选择按好评数来进行排序，从而选出好评率最高的手机。在这个过程，就用到了排序的思想。
再如，我们的大学按照教学资源以及教学能力，也能进行排序：
当然，生活中还有很多例子都是用到了排序的思想。这就是所谓处处有排序！
好了，在了解完排序的重要性之后，我们就要正式迈入学习插入排序和希儿排序的殿堂中了。
2. 插入排序
插入排序，通常我们也称它为直接插入排序。
2.1 基本思想
在一个有序的数组中，按照一定的规则插入待排序的数字。
详细一点说的话，就是：
算法思路：
先从单趟排序讲起，我们可以选择待插入的数字与从排序好的数组末端的数进行比较。若发现该值比待插入的数字要大，则将盖子往后挪动一位，接着继续往前面进行比较。若发现该值比待插入的数字要小，说明该值的后面一个位置就是待插入数字应该插入的位置，我们就可以结束循环了。
单趟排序讲完了之后，就可以将一个完整的插入排序了。
如果你真的认证解读了单趟插入排序的思路，你会发现插入排序不过如此！
其实一个完成的插入排序就是在循环地跑单趟排序，循环地初始条件为从待插入数组的第二个元素小标开始。每当单趟排序跑完之后，我们都得设置循环条件的值(一开始比较数组末端的位置)。因为你已经排好了部分数组，每当来一个新数字就得在拍好数组中插入，重复上述过程。
下面我给大家展示插入排序算法的动图，希望大家能够结合上述的话语，仔细观看：
2.2 插入排序的代码实现
void InsertSort(int* a, int n){
for (int i = 1; i < n; i++)
{
int end = i - 1; //待排序数组的末端
//也可以写成int tmp = a[end + 1];
int tmp = a[i]; //tmp存放的是待插入的数值
while (end >= 0)
{
if (tmp < a[end]) //待插入数字与数组末端的值进行比较
{
a[end + 1] = a[end];
end--;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}
2.3 插入排序算法总结
根据上面的代码，我们可以总结出一些关于插入排序算法的特征：
元素集合越接近有序，直接插入排序算法的时间效率就越高
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
，它是一种稳定的排序算法
稳定性：稳定
3. 希尔排序
希尔排序又称缩小增量排序。
3.1 基本思想
先选定一个整数(gap)，把待排序的数据分成个别组。分组的标准就是所有距离为gap的数据分在同一组，并对每一组内的记录进行排序。然后，缩小gap的值，重复上述分组和排序的工作。当gap = 1时，就相当于直接插入排序了。
上面这个思想很重要，是理解希尔排序的核心！
给大家举个例子：
3.2 希尔排序的代码实现
void ShellSort(int* a, int n){
int gap = n;
while (gap > 1)
{
//gap /= 2;
gap = gap / 3 + 1;
for (int j = 0; j < gap; j++)
{
//就是在对每组(隔gap位置的数字)的数据进行插入排序
for (int i = j; i < n; i += gap)
{
int end = i - 1;
int tmp = a[i];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + 1] = a[end];
end--;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}
}
3.3 希尔排序的特征总结
