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

【数据结构】排序算法系列——插入排序（附源码+图解）

news 2025/7/17 21:11:52

插入排序

算法思想

插入排序的算法思想其实很容易理解，它秉持着一个不变的循环：比较->交换->比较->交换…因为我们排序最终的目的是要得到递增或者递减的数据，那么在原有的数据中，我们可以将数据依次两两进行比较：

如果是升序，那么就将较小的放在较大的前面
如果是降序，那么就将较大的放在较小的前面

图解

请添加图片描述

我们看图解中，单次比较过程中，拿出来比较的数只会同它左侧的数进行比较，而被比较的数随着比较结束也会根据具体情况向后移动或者是进行交换，向后移动的过程也称为——补位。在全程的比较中，随着补位和交换的进行，进行比较操作的数只会与曾经进行过比较操作的数进行比较——简单来说，就是比较与被比较是交替进行的。我们总结插入排序算法的核心思路——将待排列元素划分为「已排序」和「未排序」两部分，每次从「未排序的」元素中选择一个插入到「已排序的」元素中的正确位置。

C语言代码分析

//升序情况
void InsertSort(int* arr, int n)
{int end = n - 1;//从最后一个数据开始进行比较int tmp = arr[end];//保存最后一个数据while (end >= 0){if (tmp <= arr[end])//当tmp小于等于arr[end]时，说明tmp还没有找到合适的位置{arr[end + 1] = arr[end];//那么就将arr[end]向后移动end--;//继续向前比较}else//当tmp大于arr[end]时，说明tmp已经找到了合适的位置{break;//那么就直接退出循环}}arr[end + 1] = tmp;
}//降序情况
void InsertSort2(int* arr, int n)
{int begin = 0;//从第一个数据开始进行比较int tmp = arr[begin];//保存第一个数据while (begin <= n - 1){if(tmp>=arr[begin])//当tmp大于等于arr[begin]时，说明tmp还没有找到合适的位置{arr[begin - 1] = arr[begin];//那么就将arr[begin]向后移动begin++;//继续向后比较}else//当tmp小于arr[begin]时，说明tmp已经找到了合适的位置{break;//那么就直接退出循环}arr[begin + 1] = tmp;
}