图文详解排序算法——直接插入法（附C语言实现源码）

大家好，欢迎来到IT知识分享网。

目录

算法思想

1.概念介绍

2.实例讲解

实现细节

1.实现源码

2.关键点讲解

算法分析

1.时间复杂度

2.空间复杂度

3.稳定性

算法思想

1.概念介绍

      什么是直接插入排序？

      我们举一个生活里的例子，打扑克牌。

      抽取卡牌时，先一张一张抽取，在抽取的过程中，每抽一张拿到手，就把这张卡拿大小插入正确的位置。

      直接排序的思想跟抽卡排序的思想非常相似，区别在于直接排序相当于已经拿到了所有无序的卡牌，而我们抽牌时则是抽到一张排一张。

      直接排序排单趟：

      假设，数组前半部分有序（排升序），使用直接排序排a[i]，是用a[i]与前一个数a[i-1]进行比较，a[i-1]较大，则使a[i-1]向后覆盖a[i]（因而此处也需要用一个变量tmp保存需排序数据a[i]值），循环向前将数组数据与tmp进行比较，直到a[i]<tmp，则将tmp插入a[i]的后一位。

      直接排序排整体：

      要使整体有序，则将需排序数组的第一个数据看做有序部分，剩余数据看做无序部分，在嵌套一层循环，使剩下的数据依次插入有序部分。

2.实例讲解

     给定一个需要进行直接排序的数组a[5]如下：（对该数组排升序）

按照上述思路，将a[0]看做有序部分，剩下的看做无序部分，依次将无序数据插入进有序部分

此时相关变量初始化化情况：tmp=a[1]   用于记录要排序的数据  ; hole=1  用于记录要插入数据的位置，初始值为需排序数据原本的位置

      1.我们首先来对a[1]开始尝试来排一次单趟：tmp=10 hole=1

将tmp与a[0]进行比较，tmp大，满足升序，因此直接执行a[hole]=tmp，将数据a[1]放在原地

       2.对a[2]开始排序：tmp=8 hole=2

tmp依次往前与a[1]比，tmp小，大值向后覆盖，此时将a[1]往后覆盖a[2]，此时a[1]的位置空出，将hole指向空位1

将tmp再次向前与a[0]比较，此时tmp较大，满足升序，则直接执行a[hole]=tmp，即将tmp放入空出的位置

      3.按照上述所说的操作，对剩下的a[3]、a[4]依次进行排序

实现细节

1.实现源码

//直接插入排序(原地) //思想： // （整体） // 1.将要排序的数据看成两部分：有序和无序 // 2.将无序的部分一个一个插入有序部分，完成排序 // （单趟） // 3.（升序排）无序的数据从后向前依次比较，需排序数据较大则插入（插在比较数据前），较小则使比较的数据后移一位 // 4.在移动过程中，使用变量保存需要排序的数据，较小比较数据后移，覆盖后一位数据 //函数设计：传入需要比较的数组，数组长度，在函数中打印排序完成的数组 void insertsort(int* arr, int arrsize) { int cursize; //已经有序的部分下标边界 int hole; //每次数据挪动留出来的位置 for ( cursize = 0; cursize <= arrsize - 1 - 1; cursize++) //cursize不能等于arrsize-1，否则arr[cursize+1]会越界 { hole = cursize + 1; int tmp = arr[cursize + 1]; //需要比较无序数据的值 //单趟 for (int i = cursize; i >= 0; i--) { //需排序数较小，比较数据向后挪动 if (arr[i] > tmp) { arr[i + 1] = arr[i]; hole = i; } //需排序数较大或相等，跳出循环 else { break; } } arr[hole] = tmp; } //打印排序好的数据 for (int i = 0; i < arrsize; i++) { printf("%d ", arr[i]); } } 

2.关键点讲解

• 由于在与需排序数字a[i]比较过程中，较大的数字会向后覆盖掉a[i]，因此需要使用变量tmp来保存a[i]的值
• 变量hole为每趟排序中，该排序的数据应该存放的位置下标，初始化为该趟需比较数a[i]的位置i

注1：假设在有序部分找到比a[i]小的数据a[j]，不能直接使a[j+1]=tmp，而是需要使用hole记录每次需要存放的位置。

这是因为要避免如下情况：

在上述数组中，按直接排序的思想使a[1]与a[0]进行比较，a[0]较大，向后覆盖a[1]，此时若使用上述语句，则会使排序失败。

注2：hole变量需要使用该趟的需要排序的a[i]的位置i进行初始化，若随意使用0来进行初始化，则会忽略以下情况：

当对a[1]进行排序时，a[1]与a[0]比较，a[1]大，跳出循环，a[hole]=tmp，实际上变成了a[0]=4，使排序出错

算法分析

1.时间复杂度

最好的情况：O(n)

要排升序，数组本身有序为升序，只需要再依次比较，原地插入就行

最坏的情况：O(n^2)

要排升序，数组为逆序，假设排a[i]，a[i]前的数据需要向后覆盖i次，一共有j个数据，数据覆盖次数构成等差数列

2.空间复杂度:O(1)

直接插入排序为原地排序，不需要为了排序额外开辟空间

3.稳定性

排序算法的稳定性看的是，两个拥有相同值的数据，在经过排序后对于排序前两者的相对前后位置是否发生改变

注：需要注意的是，算法的稳定性并完全不取决于算法的思想，而是具体要看代码实现

在上述的直接插入排序代码中，比较数据和需排序数据相等的情况下，需排序的数据并未改到比较数据的位置，即并未改变两者的相对位置，因此，它是稳定的

上述就是直接插入排序的相关知识啦，如果有不理解的地方可以在评论区提出来哦，我会及时回复的！