初阶数据结构（C语言实现）——6.1插入排序详解（思路图解+代码实现）

1 插入排序基本思想：

直接插入排序是一种简单的插入排序法，其基本思想是把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。

实际中我们玩扑克牌时，就用了插入排序的思想。接牌的时候，第一张牌我们直接拿手里，然后第二张牌就会按我们的习惯，左边小，右边大，（或者左边大，右边小）去放牌。这就是插入排序的思想。

插入排序主要分为直接插入排序和希尔排序，后面分别先介绍两类排序算法思想，然后紧跟代码实现。

2 直接插入

2.1 直接插入排序思想：

当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移

直接插入排序的特性总结：

• 元素集合越接近有序，直接插入排序算法的时间效率越高
• 时间复杂度：O(N^2)
• 空间复杂度：O(1)，它是一种稳定的排序算法
• 稳定性：稳定

2.2 直接插入排序代码实现：

• 直接插入排序思路图解

将8，5，1插入到2，4，7中，5和1是两种情况。

1. tem = 5时和end = 7比较，tem < end，
   end–,继续和4比较大于4，所以7后移，然后将tem赋值给end+1的位置，
2. tem = 1时 和end = 7比较，一直比较到2.
   tem= 1 小于 end = 2 所以end –
   此时end走到头，结束，将 2,4，7 均向后移动。
   然后将tem =1 赋值给end+1的位置。
   

2.2.1 单趟直接插入排序实现

//升序
void insertSort(int* a, int n)
{//先写单趟排序，再整体排序int end ;//end是0位置int tem ;//tem 就是end后面1个位置while (end >= 0){if (tem < a[end]){//一个一个插入，当要插入值小于end位置的值，end位置往后的值都要往后移a[end + 1] = a[end];--end;//更新end的值}else{break; //这里是比较巧妙的做法，当我们插入值大于end的时候直接跳出，}}a[end + 1] = tem; //不论我们分析的1或者5两种情况，tem的值都赋值给了end+1位置
}

2.2.2 整体直接插入排序实现

//升序
void insertSort(int* a, int n)
{int i = 0;for (i = 1; i < n ; i++) //从1 开始从n结束，如果是0开始就是n-1结束{//先写单趟排序，再整体排序int end = i-1;//end是0位置int tem =a[i];//tem 就是end后面1个位置while (end >= 0){if (tem < a[end]){//一个一个插入，当要插入值小于end位置的值，end位置往后的值都要往后移a[end + 1] = a[end];--end;//更新end的值}else{break;}}a[end + 1] = tem;}}

• 验证

3 希尔排序( 缩小增量排序 )

3.1希尔排序( 缩小增量排序 )思想

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

希尔排序的特性总结：

• 希尔排序是对直接插入排序的优化。
• 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
• 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些书中给出的希尔排序的时间复杂度都不固定：

《数据结构(C语言版)》— 严蔚敏

《数据结构-用面相对象方法与C++描述》— 殷人昆

我们的gap是按照Knuth提出的方式取值的，即gap/=2 或者 gap = gap /3 +1，而且Knuth进行了大量的试验统计，暂时就按照：O(n^1.25) ~ O(1.6*n^1.25)来算

• 稳定性：不稳定

3.2 希尔排序代码实现

3.2.1单趟排序代码实现

• 单趟希尔排序思路图解

间隔为gap分为一组对每组数据插入排序 gap = 3
蓝色是一组
橙色是一组
绿色是一组

• 单趟希尔排序代码实现

//希尔排序
void shellSort(int* a, int n)
{int i = 0;int gap = 3; //这是我们自己随便定的for (i = 0; i < n-1; i += gap){int end= i; //end最开始就是0int tem = a[i + gap];//tem 是end后一个位置（间隔gap)while (end >= 0){if (tem < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tem;}
}

3.2.2 gap组希尔排序代码实现1—外面套for循环

这里的思路就是分了gap组，所以最外层加了一个for循环，相当于，先实现蓝色组的插入排序，再实现橙色组的插入排序，最后实现绿色组的插入排序。

//希尔排序
void shellSort(int* a, int n)
{int i = 0;int gap = 3;int j = 0;for (j = 0; j < gap; j++) //gap 是几 就分几组，所以在最外层加一层循环{for (i = j; i < n - gap; i += gap)//这里i 从j开始，最开始{int end = i; //end最开始就是0int tem = a[i + gap];//tem 是end后一个位置（间隔gap)while (end >= 0){if (tem < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tem;}}
}

3.2.3 gap希尔排序代码实现2——不分组进行，同步进行

• 代码详细图解

i = 0

i = 1

i = 2

i = 3

i = 4

i = 5

i= 6

• 实现代码

//希尔排序
void shellSort(int* a, int n)
{int i = 0;int gap = 3;int j = 0;
#if 0for (j = 0; j < gap; j++) //gap 是几 就分几组，所以在最外层加一层循环{for (i = j; i < n - gap; i += gap)//这里i 从j开始，最开始{int end = i; //end最开始就是0int tem = a[i + gap];//tem 是end后一个位置（间隔gap)while (end >= 0){if (tem < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tem;}}
#endif
#if 1for (i = j; i < n - gap; i++)//这里i 从j开始，最开始{int end = i; //end最开始就是0int tem = a[i + gap];//tem 是end后一个位置（间隔gap)while (end >= 0){if (tem < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tem;}
#endif
}

• 代码验证

经过3.2.2 和3.2.3 小结我们发现最终结果并不是有序的，这说明我们的gap取值不够精确

3.2.4 希尔排序代码最终实现版本（采用3.2.3的实现思想）

gap的取值，目前我们采用gap /=2 或者 gap = gap/3+1

//希尔排序
void shellSort(int* a, int n)
{int i = 0;int gap = n;int j = 0;
#if 0for (j = 0; j < gap; j++) //gap 是几 就分几组，所以在最外层加一层循环{for (i = j; i < n - gap; i += gap)//这里i 从j开始，最开始{int end = i; //end最开始就是0int tem = a[i + gap];//tem 是end后一个位置（间隔gap)while (end >= 0){if (tem < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tem;}}
#endif
#if 1while (gap > 1){gap /= 2;for (i = j; i < n - gap; i++)//这里i 从j开始，最开始{int end = i; //end最开始就是0int tem = a[i + gap];//tem 是end后一个位置（间隔gap)while (end >= 0){if (tem < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tem;}}
#endif
}

• 验证1

• 验证2

4 附录-插入排序源码

4.1 sort.h

#pragma once
#include<stdio.h>
void printArray(int* a, int n);
void insertSort(int* a, int n);
void shellSort(int* a, int n);

4.2 sort .c

#define _CRT_SECURE_NO_WARNINGS 1
#include"20250320_sort.h"void printArray(int* a, int n)
{int i = 0;for (i = 0; i < n; i++){//printf("%d ", *(a + i));printf("%d ", a[i]);}printf("\n");
}//升序
void insertSort(int* a, int n)
{int i = 0;for (i = 1; i < n; i++) //从1 开始从n结束，如果是0开始就是n-1结束{//先写单趟排序，再整体排序int end = i - 1;//end是0位置int tem = a[i];//tem 就是end后面1个位置while (end >= 0){if (tem < a[end]){//一个一个插入，当要插入值小于end位置的值，end位置往后的值都要往后移a[end + 1] = a[end];--end;//更新end的值}else{break;}}a[end + 1] = tem;}}//希尔排序
void shellSort(int* a, int n)
{int i = 0;int gap = n;int j = 0;
#if 0for (j = 0; j < gap; j++) //gap 是几 就分几组，所以在最外层加一层循环{for (i = j; i < n - gap; i += gap)//这里i 从j开始，最开始{int end = i; //end最开始就是0int tem = a[i + gap];//tem 是end后一个位置（间隔gap)while (end >= 0){if (tem < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tem;}}
#endif
#if 1while (gap > 1){//	gap /= 2;gap = gap/3 + 1;for (i = j; i < n - gap; i++)//这里i 从j开始，最开始{int end = i; //end最开始就是0int tem = a[i + gap];//tem 是end后一个位置（间隔gap)while (end >= 0){if (tem < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tem;}}
#endif
}

4.3 sortTest.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"20250320_sort.h"void insertTest()
{int a[] = { 3,5,7,8,2,0,1 };int size = sizeof(a) / sizeof(a[0]);printArray(a, size);insertSort(a, size);printArray(a, size);
}void shellTest()
{int a[] = { 9,1,2,5,7,4,8,6,3,5};int size = sizeof(a) / sizeof(a[0]);printArray(a, size);shellSort(a, size);printArray(a, size);
}
int main(){// insertTest();shellTest();return 0;
}