01数据结构-插入排序
前言
我们前面讲的都是数据的结构，我们数据有很多元素，那这么多的元素我们该如何去组织呢？线性结构还是非线性结构呢？组织完数据中的元素后我们需要对这些元素做一定的处理，主要的处理方案就是排序，查找。
1.排序算法
要求数据有序存放。什么叫有序呢？我们就需要对数据进行唯一标识(key)，我们要保证唯一标识的有序，一般默认的有序就是从小到大的排列。由于排序有很多，我们对排序分了几类。学的算法就是在这3类各选一种。
排序的特性有:
内排序：数据完全存放在内存中，无需访问外部存储器。
外排序：数据无法全部装入内存，需借助外部存储（如硬盘），排序过程中需频繁读写外存
就地排序
空间复杂度：仅需常数级额外空间（如几个临时变量），不依赖输入数据规模，空间复杂度为 O(1)。
是否修改原数据：直接在原数组上交换或移动元素，会改变原始数据顺序
典型算法：冒泡排序、选择排序、插入排序、快速排序、堆排序非就地排序：
空间复杂度：需额外存储空间，通常与输入数据规模成正比（O(n)），如额外数组或桶。
是否修改原数据：可能生成新副本，原数据保留（部分算法如归并排序需额外空间但不改变原数组，需结合具体实现判断）。
典型算法：归并排序、计数排序、基数排序、桶排序。稳定排序：排序后，相等元素的相对位置与排序前一致。
示例：对 [3, 1, 2, 3]按升序排序，稳定排序后两个 3的原始顺序不变，结果为 [1, 2, 3, 3]。非稳定排序：排序后，相等元素的相对位置可能改变。
示例：对 [3, 1, 2, 3]按升序排序，非稳定排序可能将后一个 3移到前面，结果为 [1, 2, 3, 3]（顺序可能变化）。
之前我们说过评价一个算法性能好坏是看这个算法所耗费的事件复杂度和空间复杂度。由于我们的排序要保证所有传进来的数据都有效，我们随机生成n个数据，可能1w,可能10w个元素，然后设计一个测试框架里面包含：准备数据，执行排序，验证结果，输出执行时间，然后我们的设计者往这个框架里面输入数据即可，同时我们把自己设计的排序如冒泡排序、选择排序也传进去就能实现对应排序的复杂度，下面我们来看一看怎么设计这个框架。
2.框架搭建
我们先来看一下框架的搭建，后面我们写的排序都是基于这个框架。
数据结构设计；
typedef int keyType;
typedef struct {
keyType key; // 查找表中每个数据元素的关键值
void *data; // 数据的其他区域
}Element;
typedef struct {
Element *data; // 存放查找表中数据元素的首地址
int length; // 查找表的元素个数
}SortTable;
我们需要定义表中每个数据元素的关键值，void *data在这个框架里面只是表示占位，实际工程中可能会有其他表示，由于数据量比较大，我们不能把数据放在栈中应该在堆上申请，和之前的思路一样，我们用一个 Element *类型的指针来指向堆中数据的首地址。用int length;来限制其访问。
对表的操作:
创建表:SortTable *generateLinearArray(int n, int swapTimes)；
/* 产生n个随机数的排序表，值的范围是[low, high] */
SortTable *generateRandomArray(int n, int low, int high) {
//申请表
SortTable *table = malloc(sizeof(SortTable));
if (table == NULL) {
fprintf(stderr, "sort table malloc failed!\n");
return NULL;
}
table->length = n;
table->data = (Element *) malloc(sizeof(Element) * n);
if (table->data == NULL) {
fprintf(stderr, "element malloc failed!\n");
free(table);
return NULL;
}
//产生随机数
srand(time(NULL) + 1);
for (int i = 0; i < n; ++i) {
table->data[i].key = (rand() % (high - low + 1)) + low;
table->data[i].data = NULL;
}
return table;
}
作用 ：生产出的样本数据完全随机、值域可控的乱序数组，测试平均情况下的排序性能（时间、比较次数、交换次数等）
复制数据:SortTable *copySortTable(SortTable *old);
/* 拷贝一个排序表，使用同样的数据进行不同排序算法的测试 */
SortTable *copySortTable(SortTable *old) {
SortTable *table = (SortTable *) malloc(sizeof(SortTable));
table->length = old->length;
table->data = malloc(sizeof(Element) * old->length);
for (int i = 0; i < old->length; ++i) {
table->data[i].key = old->data[i].key;
table->data[i].data = old->data[i].data;
}
return table;
}
作用：把同一份原始数组复制出多份，让不同排序算法跑完全一样的输入，保证实验对比公平
几乎有序的表:SortTable *generateLinearArray(int n, int swapTimes);
/* 交换a和b的元素值 */
void swapElement(Element *a, Element *b) {
Element tmp;
memcpy(&tmp, a, sizeof(Element));
memcpy(a, b, sizeof(Element));
memcpy(b, &tmp, sizeof(Element));
}
/* 产生n个随机交换swapTimes次的有序顺序表 */
SortTable *generateLinearArray(int n, int swapTimes) {
SortTable *table = malloc(sizeof(SortTable));
if (table == NULL) {
fprintf(stderr, "sort table malloc failed!\n");
return NULL;
}
table->data = malloc(sizeof(Element) * n);
if (table->data == NULL) {
fprintf(stderr, "data malloc failed!\n");
free(table);
return NULL;
}
table->length = n;
for (int i = 0; i < n; ++i) {
table->data[i].key = i;
table->data[i].data = NULL;
}
// 在已经有序的排序表中，交换swapTimes次
srand(time(NULL) + 2);
for (int i = 0; i < swapTimes; ++i) {
int pos1 = rand() % n;
int pos2 = rand() % n;
swapElement(&table->data[pos1], &table->data[pos2]);
}
return table;
}
作用:产生出基本有序、只随机交换过 swapTimes 次的数组，测试排序算法在“几乎有序”输入下的表现；很多 O(n²) 算法会退化，而自适应算法（如插入排序、Timsort）会非常快
释放表：void releaseSortTable(SortTable *table)；
/* 释放table */
void releaseSortTable(SortTable *table) {
if (table) {
if (table->data) {
free(table->data);
}
free(table);
}
}
测试接口:
enum sortStatus{success, failed};
// 检查排序表里的数据，是否是从小到大排序
static enum sortStatus checkData(const SortTable *table) {
for (int i = 0; i < table->length - 1; ++i) {
if (table->data[i].key > table->data[i + 1].key) {
printf("Check Sort Data Failed: %d : %d\n", table->data[i].key, table->data[i + 1].key);
return failed;
}
}
return success;
}
// 排序算法函数的别名
typedef void (*sortHandler)(SortTable *);
/* 测试sortName的排序算法，算法通过sort传递函数名，数据以table传入 */
void testSort(const char *sortName, sortHandler sort, SortTable *table) {
clock_t start = clock();
sort(table);
clock_t end = clock();
if (checkData(table) == failed) {
printf("%s failed!\n", sortName);
return;
}
printf("%s cost time: %fs.\n", sortName, (double) (end - start) / CLOCKS_PER_SEC);
}
写了一个枚举类型和检查排序表里的数据，是否是从小到大排序的函数，用来测试sortName的排序算法是否正确，由于我们需要用到回调函数，在 C 里，“回调函数”本质就是把一段可执行代码的地址交给另一个函数，让它在合适的时候“回头调用（call back）”。能表达“地址”这一概念的，在标准 C 中主要就是函数指针。所以我们要在sortHandler前加*表示是函数指针。它指向“接受 SortTable为参数 、返回 void” 的函数。在void testSort(const char *sortName, sortHandler sort, SortTable *table) 函数中传的参数是：排序的名字，排序函数的首地址，传的数据，进去函数的一瞬间开始计时，排序好后退出计时，如果算法失败则退出，如果成功则打印出执行算法的时间。
#ifndef INSERT_SORT_H
#define INSERT_SORT_H
#include"..//sortHelper.h"
void insertSort(SortTable *table);
#endif //INSERT_SORT_H
我们在insertSort.h头文件里添加测试框架并写好排序的接口
#include "insertSort.h"
int main() {
int n=10000;
SortTable *table1=generateRandomArray(n,0,n+5000);
testSort("insertSort",insertSort,table1);
releaseSortTable(table1);
return 0;
}
就可以在main函数中进行测试了。
3.插入排序
插入排序是所有排序方法中最简单的一种算法，其主要的实现思想是将数据按照一定的顺序一个一个的插入到有序的表中，最终得到的序列就是已经排序好的数据。
如图1在无序区中找到要插入的数据，在有序区中把找到前一个数比它大后一个数比它小的数插入进去，把后面的元素往后移
图1
3.1直接插入排序
在玩扑克牌的时候，我们抽到一张牌的时候，都是将它插入到当前手中牌的合适位置的。直接插入排序也是这样的思想。
插入排序的思想是：
将待排序序列分成两个序列，前面的序列保持有序，依次选取后面的序列的元素，在前面的序列中进行插入。初始时，有序序列的⻓度为1。
例子:
给定序列 [9 , 20 , 13 , 10 , 12 ] 。初始状态如下：
分成的两个序列如下：
也就是说，此时我们将数组当中的第一个元素9当作有序元素。
第一次插入：将20和9做比较，20>9，顺序没有问题。不动。
第二次插入：将13与20比较，13<20，此时20就要先到13的位置。再跟9比较，13>9，那么此时将13插入到9后面。
第三次插入，将10和20比较，10<20，20去10的位置，再将10和13比较，10<13，则13也往下移动，再将10和9比较，10>9，则将10插入到9的后面。
第四次插入：将12和20比较，12 <20，20后移，再将12和13比较，12<13，13后移，再将12和10比较，12 > 10,将12插入到10的后面。
3.1.1直接排序代码实现
void insertSort(SortTable* table) {
for (int i = 1; i < table->length; ++i) {
if (table->data[i].key < table->data[i - 1].key) {
// 用j辅助索引来找到待插入元素该放的位置
int j = i - 1;
//备份table->data[i]的值
Element temp = table->data[i];
// 从[0...i-1]
while (j >= 0 && table->data[j].key > temp.key) {
table->data[j + 1] = table->data[j];
j--;
}
table->data[j + 1] = temp;
}
}
}
我们把第一个元素默认为有序的，从第2个元素(第一个索引)开始到最后一个元素开始循环排序，我们需要不断地与有序区中0到i-1个数据进行对比找到第一个比table->data[i].key 小的那个数(因为我们的有序区是从小到大排序的)，用temp备份table->data[i]的值，最后找到了就把temp赋值给那个table下的索引就行，在找值得过程中，我们需要j始终大于0，不能超出数组的范围，还需要table->data[j].key比temp.key大，如果小了就说明找到了，退出循环即可， 在循环中我们不断把数据往后移动 table->data[j + 1] = table->data[j];
来测试一下：
#include "insertSort.h"
int main() {
int n1=10000;
int n2=100000;
SortTable *table1=generateRandomArray(n1,0,n1+5000);
SortTable *table2=generateRandomArray(n2,0,n2+5000);
testSort("insertSort",insertSort,table1);
testSort("insertSort",insertSort,table2);
releaseSortTable(table1);
return 0;
}
结果:
D:\work\DataStruct\cmake-build-debug\04_Sort\InsertSort.exe
insertSort cost time: 0.042000s.
insertSort cost time: 3.288000s.
进程已结束，退出代码为 0
n扩大十倍，时间扩大了100倍左右，很明显这种算法的时间复杂度是n2,原因也很简单在void insertSort(SortTable* table)进行了两次循环。
在工程中大部分的数据都是比较有序的，只有少部分无序，那我们的算法对这种序列是什么效果呢，下面就要用到写的SortTable *generateLinearArray(int n, int swapTimes);函数来测了
#include "insertSort.h"
int main() {
int n1=100000;
//int n2=100000;
SortTable *table1=generateRandomArray(n1,0,n1+5000);
//SortTable *table2=generateRandomArray(n2,0,n2+5000);
SortTable *table3=generateLinearArray(n1,10);
testSort("insertSort",insertSort,table1);
testSort("LinearSort",insertSort,table3);
//testSort("insertSort",insertSort,table2);
releaseSortTable(table1);
return 0;
}
结果：
D:\work\DataStruct\cmake-build-debug\04_Sort\InsertSort.exe
insertSort cost time: 3.387000s.
LinearSort cost time: 0.000000s.
进程已结束，退出代码为 0
可以看到在排序大多数有序的表时用到的时间非常非常少，甚至是接近0s。此时，这儿的时间复杂度就变为了O(n)，因为大部分都是有序的，排列那些无序的数据的时候就很少有会进入第二重循环的了。
3.2折半插入排序
折半插入排序是插入排序的改进算法，核心是利用折半查找优化插入位置的定位效率，减少比较次数，但元素移动次数不变，时间复杂度仍为 O(n2)，空间复杂度为 O(1)，且保持排序稳定性。
核心思想
在已排序序列中，通过折半查找快速定位待插入元素的插入位置，替代传统插入排序的逐个比较，降低比较次数。
算法步骤
1.初始化：将待排序数组分为有序区（初始为第一个元素）和无序区。
2.折半查找：对于无序区的每个元素，用折半查找在有序区中确定插入位置：
3.若待插入元素小于中间元素，向左半区继续查找；否则向右半区查找，直至定位插入点。
折半插入排序我们用的很少，因为元素移动次数不变，所以这里就不实现具体代码了，这里我用AI大概写了一下。
//折半插入排序
void binaryInsertSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int temp = arr[i]; // 待插入元素
int low = 0, high = i - 1;
// 折半查找插入位置
while (low <= high) {
int mid = (low + high) / 2;
if (temp < arr[mid]) {
high = mid - 1;
} else {
low = mid + 1;
}
}
// 移动元素，腾出插入位置
for (int j = i - 1; j >= high + 1; j--) {
arr[j + 1] = arr[j];
}
arr[low] = temp; // 插入元素
}
}
3.32-路插入排序
2-路插入排序是折半插入排序的改进版本，通过辅助数组+环状结构减少元素移动次数，核心思想是将待排序元素分为“小于最小值”和“大于最大值”两类，分别插入辅助数组的两端，中间元素通过移动填补空位。
核心思想
1.辅助数组：额外开辟与原数组等长的空间d，将原数组首元素arr[0]作为初始有序序列的中间值存入d[0]，并设置first（指向最小值）和final（指向最大值）指针。
2.
分类插入：
若待插入元素arr[i] < d[first]，则插入d的左侧（循环移动左侧元素）；
若arr[i] > d[final]，则插入d的右侧（循环移动右侧元素）；
否则，在d的中间找到合适位置插入（需移动部分元素）。
3:环状处理：通过取模运算实现循环数组的边界处理，避免数组越界。
算法步骤
1.初始化辅助数组d，first=final=0，d[0]=arr[0]。
2.遍历原数组（从第2个元素开始）：根据元素大小与d[first]/d[final]的比较，决定插入位置插入时移动元素，更新first或final指针。
3.最后将辅助数组d的有序序列复制回原数组。
这里我们也不着重讲，我还是用AI写的代码：
void twoWayInsertSort(int arr[], int n) {
int d[n]; // 辅助数组
int first = 0, final = 0; // 指向最小值和最大值的指针
d[0] = arr[0]; // 初始有序序列
for (int i = 1; i < n; i++) {
if (arr[i] < d[first]) { // 插入左侧
first = (first - 1 + n) % n;
d[first] = arr[i];
} else if (arr[i] > d[final]) { // 插入右侧
final = (final + 1) % n;
d[final] = arr[i];
} else { // 插入中间
int k = (final + 1) % n;
while (d[(k - 1 + n) % n] > arr[i]) {
d[k] = d[(k - 1 + n) % n];
k = (k - 1 + n) % n;
}
d[k] = arr[i];
final = (final + 1) % n;
}
}
// 复制回原数组
for (int i = 0; i < n; i++) {
arr[i] = d[(first + i) % n];
}
}
3.4希尔排序
希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n^2）的第一批算法之一。
基本思想
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
简单插入排序很循规蹈矩，不管数组分布是怎么样的，依然一步一步的对元素进行比较，移动，插入，比如[5,4,3,2,1,0]这种倒序序列，数组末端的0要回到首位置很是费劲，比较和移动元素均需n-1次。而希尔排序在数组中采用跳跃式分组的策略，通过某个增量将数组元素划分为若干组，然后分组进行插入排序，随后逐步缩小增量，继续按组进行插入排序操作，直至增量为1。希尔排序通过这种策略使得整个数组在初始阶段达到从宏观上看基本有序，小的基本在前，大的基本在后。然后缩小增量，到增量为1时，其实多数情况下只需微调即可，不会涉及过多的数据移动。
我们来看下希尔排序的基本步骤，在此我们选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2…1}，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。
例子:
原始数组 以相同的颜色为一组
初始增量gap=length/2=5，意味着整个数组被分为5组，[8,3],[9,5],[1,4],[7,6],[2,0]。
然后我们对这五组分别进行直接插入排序，结果就变成
可以看⻅例如3，5，6这些小元素就在前面了，然后缩小增量gap = 5/2 = 2，将数组分成两组
对以上的两组再分别进行直接插入排序，结果如下。此时整个数组的有序程度就更近一步了。
再缩小增量，gap=2/2=1.此时整个数组为1组。[0,2,1,4,3,5,7,6,9,8]。
此时，只需要对以上数列简单微调。无需大量的移动操作即可完成整个数组的排序。
性能
本文介绍了希尔排序的基本思想及其代码实现，希尔排序中对于增量序列的选择十分重要，直接影响到希尔排序的性能。我们上面选择的增量序列{n/2,(n/2)/2…1}(希尔增量)，其最坏时间复杂度依然为O(n2)。这是为什么呢？
到底什么地方出了问题呢？我们再来看一个坏的例子，假设这是我们的初始序列，如果用shell的增量序列我们会一开始怎么做呢？这一共有16个数字
我们一开始就做8间隔的排序，8间隔的排序我们就从1开始，然后往后数7个数字，就是排1和5，发现本来就是有序的，什么都不用动，然后下一个，就是9和13，也是有序的，2和6，还是有序的，10和14还是有序的，继续往后看，就会发现，我做了一个8间隔的排序，结果哪个元素都没有动，大家保持原样的走下来了，下一步我要做4间隔的，结果还是全部都是有序的。
结果这趟又白跑了，2间隔的排序，你应该猜到结果了，还是什么都没干，最后要达到有序，还是得靠我们1间隔的排序。结果这趟又白跑了，2间隔的排序，你应该猜到结果了，还是什么都没干，最后要达到有序，还是得靠我们1间隔的排序。
所以这其实是一个让人非常囧的情况，就是前面我白做了3趟排序，然后最后还是跟原始的插入排序一样，还不如一开始我就直接做原始的插入排序，那到底什么地方出了问题呢？我们通过仔细的分析
会发现因为它的增量元素不互质，8是4的倍数，4是2的倍数，2是1的倍数，那么小的增量就有可能在后面的排序里面根本不起作用。
3.4.1希尔排序代码实现
void shellSort(SortTable* table) {
//分组
for (int gap = table->length / 2; gap > 0; gap /= 2) {
//插入排序，步长变了
for (int i = gap; i < table->length; ++i) {
Element temp = table->data[i];
int j;
for (j = i; j >= gap && table->data[j - gap].key > temp.key; j -= gap) {
table->data[j] = table->data[j - gap];
}
table->data[j] = temp;
}
}
}
先是一个for循环来处理增量，最外层的for循环里面其实就是直接插入排序的逻辑，只不过步长变了，之前要在数据空间中一个一个地比较，所以是i–,这里是从gap开始，递减是从j开始–gap。配合着上述我举得例子大家应该就理解了。
我们用同样的数据来测，要用到我们写的测试框架中的SortTable *copySortTable(SortTable *old)
最后来测一下：
#include "insertSort.h"
int main() {
int n1=100000;
//int n2=100000;
SortTable *table1=generateRandomArray(n1,0,n1+5000);
//SortTable *table2=generateRandomArray(n2,0,n2+5000);
//SortTable *table3=generateLinearArray(n1,10);
SortTable *table4=copySortTable(table1);
testSort("insertSort",insertSort,table1);
//testSort("LinearSort",insertSort,table3);
//testSort("insertSort",insertSort,table2);
testSort("shellSort",shellSort,table4);
releaseSortTable(table1);
releaseSortTable(table4);
return 0;
}
结果:
D:\work\DataStruct\cmake-build-debug\04_Sort\InsertSort.exe
insertSort cost time: 3.324000s.
shellSort cost time: 0.017000s.
进程已结束，退出代码为 0
可以发现希尔排序比直接插入排序的效率高得多
今天讲的插入排序大家以理解为主，大概先写这些吧，今天的博客就先写到这，谢谢您的观看。