插入排序
插入排序的思路就像是你在整理一堆扑克牌。你先拿起第一张牌，然后拿起第二张牌，把它插入到合适的位置，使得你手上的两张牌是有序的。接着，你再拿起第三张牌，也把它插入到合适的位置，使得你手上的三张牌是有序的。依此类推，直到你把所有的牌都拿到手上，这时你手上的牌就是有序的了。
如果我们要对一个数组a进行插入排序（假设按照升序排列），我们可以这样做：
首先，我们认为数组的第一个元素a[0]是有序的。然后，我们把第二个元素a[1]插入到合适的位置，使得a[0]和a[1]是有序的。接着，我们把第三个元素a[2]也插入到合适的位置，使得a[0]、a[1]和a[2]是有序的。以此类推，直到我们把最后一个元素a[n-1]也插入到合适的位置，这时整个数组就是有序的了。
具体来说，如果我们已经知道下标为[0, end]的元素是有序的，那么如何把下标为end+1的元素插入进去呢？我们可以先把a[end+1]保存在一个临时变量tmp中，因为它很快就会被覆盖掉。然后，我们从右向左依次比较tmp和a[end]、a[end-1]、a[end-2]……等等。如果tmp比某个元素小，就把那个元素向右移动一位，为tmp腾出空间。如果tmp不比某个元素小，或者已经到达数组的左边界了，就停止移动，并把tmp放在当前空出来的位置上。
最后我们只需要控制end的变化即可。一开始end为0，表示只有一个元素是有序的。然后end逐渐增加，每次增加1，直到end为n-2时停止。这时候[0, n-2]是有序的，只需要把最后一个元素a[n-1]插入进去就完成了排序。
下面我画几张图来解释。假设原数组是[5 1 9 4 8 2 6 3 7]，那么排序的过程就是：
一开始end是0，表示[0,0]是有序的，即只有第一个数是有序的。
接着把a[1]插入，使得使得[0,1]是有序的。
下面以此类推。
即在[0., end]有序的前提下，每次都把a[end+1]插入到[0, end]中，使得[0, end+1]有序。
每次插入的详细过程是怎样的呢？请看下面的演示。
假设数组是[0 1 2 4 5 3]，end是4，表示要把a[5]插入到[0,4]中，使得整个数组有序，我们应该如何插入呢？
初始状态：
首先把a[end+1]保存到临时变量tmp中。
由于tmp比a[end]小，所以a[end+1]=a[end]，–end。
tmp依然比a[end]小，所以a[end+1]=a[end]，–end。
此时tmp比a[end]大，所以a[end+1]=tmp。
插入排序，在最坏的情况下，每次比较的次数都会比前一次多1，总的比较次数使用等差数列求和公式可得，其时间复杂度为O(N2)。由于插入排序使用常数的额外空间，其空间复杂度为O(1)。由于单趟插入排序，每次都会把最后面的数据插入到向前找到的第一个比它小（或等于）的数据之后，所以对于相同的数据，是不会改变它们的相对顺序的，即插入排序是一个稳定的排序。
void InsertSort(int* a, int n)
{
for (int i = 0; i < n - 1; ++i)
{
// 单趟插入排序
// [0, end]有序
int end = i;
// 插入end+1
int tmp = a[end + 1];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + 1] = a[end];
--end;
}
else
{
break;
}
}
// 把tmp插入到此时的end后面
a[end + 1] = tmp;
}
}
希尔排序
希尔排序的思路就像是你在打扫一间房间。你不是一次性把所有的东西都放到正确的位置，而是先按照一定的间隔分成几个小组，每个小组内部进行一次插入排序，使得每个小组内部的东西都相对有序。然后你再缩小间隔，重新分组，再进行一次插入排序，使得每个小组内部的东西更加有序。你不断重复这个过程，直到间隔为1，也就是所有的东西都在同一个小组里，这时你再进行一次插入排序，就可以把所有的东西都放到正确的位置了。
如果我们要对一个数组a进行希尔排序（假设按照升序排列），我们可以这样做：
首先，我们选择一个合适的间隔gap，比如数组长度的一半。然后我们把数组分成gap个小组，每个小组由相隔gap个元素组成。例如，如果gap为3，那么第一个小组由a[0]、a[3]、a[6]……等等组成，第二个小组由a[1]、a[4]、a[7]……等等组成，第三个小组由a[2]、a[5]、a[8]……等等组成。接着我们对每个小组进行一次插入排序，使得每个小组内部的元素都相对有序。
然后我们缩小间隔gap，比如取原来的三分之一。这时我们又可以把数组分成新的gap个小组，每个小组由相隔gap个元素组成。例如，如果新的gap为1，那么第一个小组就是整个数组。然后我们再对每个小组进行一次插入排序，使得每个小组内部的元素更加有序。
最后我们重复这个过程，直到间隔gap为1时停止。这时我们只需要对整个数组进行一次插入排序，就可以把所有的元素都排好序了。
具体来说，我们可以用一个外层循环控制间隔gap的变化，每次取原来的三分之一加一，直到为1时停止。然后我们用一个中层循环控制每个小组内部的插入排序过程。在中层循环中，我们需要从0开始向右遍历数组，每次只移动一个元素，直到到达n-gap为止。这样就可以把数组分成gap个小组，每个小组由相隔gap个元素组成。最后我们用一个内层循环控制每个小组内部的元素插入过程。在内层循环中，我们需要先把当前元素a[end+gap]保存在一个临时变量tmp中，并把它和左边相隔gap个元素的元素a[end]比较。如果tmp比a[end]小，就把a[end]向右移动gap位，为tmp腾出空间。如果tmp不比a[end]小，或者已经到达数组的左边界了，就停止移动，并把tmp放在当前空出来的位置上。这样就完成了一次插入排序。
注意：gap在不断缩小的过程中，最后一定会变成1，这时候就相当于执行了一次普通的插入排序，这是为了确保数组在最后能够完全有序。
希尔排序的时间复杂度是非常难算的，经过大量的统计，其时间复杂度大致是O(N1.3)。由于希尔排序使用常数的额外空间，其空间复杂度为O(1)。希尔排序本质上是对不同组的数据分别进行直接插入排序，会把相距gap的数据分到一组，每组之间如果存在相同的数据，同组之间，它们的相对顺序是不会改变的。但是，如果不同组中的数据存在相同的数据，那么无法保证其相对顺序是否改变。所以，希尔排序是不稳定的排序。文章来源：https://www.toymoban.com/news/detail-563252.html
void ShellSort(int* a, int n)
{
int gap = n; // 组距，即同组中两两间隔的距离
while (gap > 1) // 保证gap已经是1时不会重复循环
{
gap = gap / 3 + 1; // 保证最后一次是1
for (int i = 0; i < n - gap; ++i) // 防止end+gap越界，进行分组预排
{
// [0, end]同组的已经有序，插入end+gap
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
// 插入到end后面，保持组距
a[end + gap] = tmp;
}
}
}
总结
- 插入排序的思想：每次从未排序的数中选取一个，将其插入到已排序的数中合适的位置，保证插入后仍然有序。
- 希尔排序的思想：把数组按照一定的间隔gap分成若干组，每组的元素下标相差gap，然后对每组内的元素进行插入排序。随着gap的不断减小，每组内的元素越来越多，最终当gap减小到1时，整个数组就变成了一组，此时进行最后一次插入排序，就可以得到完全有序的数组。
- 插入排序的时间复杂度为O(N2)，空间复杂度为O(1)，是稳定的排序。
- 希尔排序的时间复杂度大致是O(N1.3)，空间复杂度为O(1)，是不稳定的排序。
感谢大家的阅读！文章来源地址https://www.toymoban.com/news/detail-563252.html
到了这里，关于插入排序和希尔排序：用C语言打造高效的排序算法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
