当前位置：首页 > ai >正文

【数据结构】排序（sort） -- 插入排序

ai 2025/8/6 21:53:08

一、插入排序

二、直接插入排序（straight insertion sort）

1. 思路介绍

2. 代码实现

3. 特性总结

三、希尔排序（Shell sort）

1. 思路介绍

2. 代码实现

3. 特性总结

四、总结

一、插入排序

常见的排序算法有：

而本篇文章要介绍的是插入排序。

插入排序可以分为 直接插入排序 和 希尔排序 。

二、直接插入排序（straight insertion sort）

1. 思路介绍

直接插入排序是一种简单的插入排序法，其基本思想是：

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。

如图是基本思想的示意图：排序思路：

将整个数据划分为有序区和无序区，初始时有序区只有一个数据，无序区包含了剩余所有待排序数据。
将无序区的第一个数据插入到有序区的合适位置中，从而使无序区减少一个数据，有序区增加一个数据。
重复步骤2，知道无序区没有数据。

对于一组数据：3，44，38，5，47，15，36，26，27，2，46，4，19，50，48 它的排序个过程如下：

排序动图如下：

排序一个数据的方法（排升序）：

将要排序数据先和有序区的最后一个数据比较，如果比该数据小，就将有序区该数据向后移动一位；如果比该数据大，就什么都不做，因为这样已经将该要排序数据排好了。排序一个数据的代码实现：

int end;// 有序区最后一个数据的下标
int tmp;// 该趟要排序的数据// 插入：将tmp插入到[0,end]区间中去
while (end >= 0)
{if (tmp < a[end]){a[end + 1] = a[end];// 后移有序区数据end--;}else{break;// 已经找到到合适位置，则退出循环}
}
a[end + 1] = tmp;// 插入合适位置

2. 代码实现

排序一组数据，就只需要遍历所有数据，逐步插入就可以了。则C语言代码实现：

// 插入排序 - 排升序
void InsertSort(int* a, int n)
{for (int i = 1; i < n; i++){int end = i - 1;// 有序区最后一个数据的下标int tmp = a[i];// 该趟要排序的数据// 插入：将tmp插入到[0,end]区间中去while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];// 后移有序区数据end--;}else{break;// 已经找到到合适位置，则退出循环}}a[end + 1] = tmp;// 插入合适位置}
}

3. 特性总结

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

元素集合越接近有序，直接插入排序算法的时间效率越高
时间复杂度：O(N^2)，最好情况：O(N)，最坏情况：O(N^2)
空间复杂度：O(1)
稳定性：稳定

三、希尔排序（Shell sort）

1. 思路介绍

希尔排序是对直接插入排序的一种改进。

希尔排序法又称缩小增量法。希尔排序法的基本思想是：

把待排序数据分割为若干子序列，再对各个子序列分别进行直接插入排序。

排序思路：

先选定一个整数gap，表示间隔，把待排序文件中所有记录分成gap个组，把所有距离为gap的记录分在同一组内，并对每一组内的记录进行直接插入排序，让整个数据接近有序。
然后，每次将gap缩小一半，重复上述分组排序的工作，让整个数据逐渐接近有序。
当到达gap = 1时，就相当于普通的直接插入排序，但此时整个数据已经非常接近有序，排序效率是非常高。

所以，当gap>1时，这就是对数据的预排序；当gap=1时，这就是普通直接插入排序。

如图是希尔排序的示意图：

排序间隔为gap的一组。

如图为假设 gap = 3 时其中一组数据的的直接插入排序：

排序间隔为gap的其中一组的代码实现：

int gap;// 间隔
for (int i = gap; i < n; i += gap)
{int end = i - gap;// 有序区最后一个数据的下标int tmp = a[i];// 该趟要排序的数据// 间隔gap插入while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];// 后移有序区数据end -= gap;}else{break;// 已经找到到合适位置，则退出循环}}a[end + gap] = tmp;// 插入合适位置
}

那么排序gap时，所有组的实现就是通过调整状态的起始位置，然后重复上述实现：

int gap;// 间隔
for (int j = 0; j < gap; j++)
{for (int i = j + gap; i < n; i += gap){int end = i - gap;// 有序区最后一个数据的下标int tmp = a[i];// 该趟要排序的数据// 间隔gap插入while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];// 后移有序区数据end -= gap;}else{break;// 已经找到到合适位置，则退出循环}}a[end + gap] = tmp;// 插入合适位置}
}

如图所示，为当gap=3时的一组排序过程：

直到一组gap值的排序后，就可以再调整gap值为原来的一半，重复这个过程就可以了。

一般来说，gap的值是可以随意取的。但

gap如果越大，那么间隔就大，排完一组的的时间就快，但这样越不接近有序；

gap如果越小，那么间隔就小，排完一组的的时间就慢，但这样越接近有序；

所以，希尔排序（Shell Sort）的间隔gap初始值通常取原数据长度的一半（即 gap = n/2），然后逐步缩小（如每次减半），最终缩小到1进行最后一次插入排序。

n/2 的间隔能确保子序列覆盖整个数组，避免遗漏元素。

2. 代码实现

希尔排序C语言实现如下：

//希尔排序
void ShellSort(int* a, int n)
{int gap = n;// 间隔while (gap > 1){gap /= 2;for (int j = 0; j < gap; j++){for (int i = j + gap; i < n; i += gap){int end = i - gap;// 有序区最后一个数据的下标int tmp = a[i];// 该趟要排序的数据// 插入while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];// 后移有序区数据end -= gap;}else{break;// 已经找到到合适位置，则退出循环}}a[end + gap] = tmp;// 插入合适位置}}}
}

可以发现这里的循环很多，所以这里可以简化一下：

void ShellSort(int* a, int n)
{int gap = n;// 间隔while (gap > 1){gap /= 2;for (int i = gap; i < n; i++){int end = i - gap;// 有序区最后一个数据的下标int tmp = a[i];// 该趟要排序的数据// 插入while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];// 后移有序区数据end -= gap;}else{break;// 已经找到到合适位置，则退出循环}}a[end + gap] = tmp;// 插入合适位置}}
}

3. 特性总结

希尔排序的特性总结：

希尔排序是对直接插入排序的优化。
当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。
希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算。一般来说，时间复杂度是 $Q(n^{1.3})$ ~ $O(n^{2})$ 之间。
空间复杂度：O(1)
稳定性：不稳定

四、总结

直接插入排序通过将待排序元素逐个插入已排序序列来实现排序，时间复杂度为O(N^2)，适用于接近有序的数据。
希尔排序是直接插入排序的改进版本，采用分组排序策略，先通过较大间隔进行预排序，再逐步缩小间隔直至1，提高了整体排序效率。
希尔排序的时间复杂度难以精确计算，但优于直接插入排序，空间复杂度均为O(1)。
两种算法的主要区别在于：直接插入排序稳定但效率较低，希尔排序不稳定但效率较高。

感谢各位观看！希望能多多支持！

查看全文

http://www.xdnf.cn/news/17001.html