内部排序——插入排序

作者：乔乔

2022 年 7 月 07 日
本文字数：1488 字
阅读完需：约 5 分钟

内部排序分为：插入排序，交换排序，选择排序，归并排序，基数排序这五种。

1.插入排序

插入排序又分为：直接插入排序，折半插入排序，2-路插入排序，希尔排序。其中希尔排序是最好用的。

直接插入排序

这个是比较好理解，但操作起来比较麻烦，不建议用这种方法。

假设我们有这样一组数：49 38 65 97 76 13 27 49

我们从第一个 49 开始排序，（49）。

一次看下一个数 38，因为 38 比 49 小，所以排在 49 前面，（38 ，49）一次按这个规律排序。

（38 49 65）

（38 49 65 97）

（38 49 65 76 97）

（13 38 49 65 76 97）

（13 27 38 49 65 76 97）

（13 27 38 49 49 65 76 97）（注：原数列中最后一个 49 与第一个 49 相同，排序时原数列最后一个 49 应排在原数列第一个 49 的后面。）

算法如下：

Void InsertSort(SqList &L) {
for (i= 2; i<L.Length; ++i )
if LT(L.r[i].key,L.r[i-1].key){
L.r[0] =L. r [1];
L. r[i] = L.r[i-1];
for (j =i-2;LT(L.r[0].key,L.r[i].key);--j)
L.r[j+1] =L. r[i];
L.r[j+1]=L.r[0];
}
}InsertSort

折半插入法

折半插入排序是在有序表中进行插入。

如图所示，1 2 3 4 为有序表，5 6 7 8 9 10 11 为待排序的子表。有序表第一个数 low，最后一个为 high，中间数 mid。子表数与 mid 比较，小于 mid 在 mid 前面进行排序，大于 mid 在 mid 后面排序。

算法：

void BInsertSort(SqList & L ) {
for (i=2;i<= L .length; ++i) {
L. r[0] = L. r [i];
low=1;high=i-1;
while (low<= high) {
m =(low + high)/2;
ifLTL.r[0].key,L.r[m].key)high=m-1;
else low = m+1;
}// while
for( j = i-1; j>= high +1;-- j) L.r[j+1] = L. r[j];
L.r[high+1]= L.r[0];
}// for
}// BInsertSort

2-路插入排序（不是很常用）

2-路插入排序是在折半插入排序的基础上的发展。其目的是减少排序过程中记录移动的次数，但为此需 n 个记录的辅助空间。

具体做法是:另设一个和 L.r 同类型的数组 d，首先将 L.r[1]赋值给 d[1l，将 d[1]看成是排好序的序列中处于中间位置的记录，然后从 L.r 中第 2 个记录起依次插入到 d1l 之前或之后的有序序列中。先将待排序记录的关键字和 d1]的关键字比较，若 L.r[i].key<d[1] .key，则将 L.r[i]插入到 d[1]之前的有序表中。反之，将 L.ril 插入到 d1l 之后的有序表中。

在实现算法时，将 d 看成一个循环向量，并设两个指针 first 和 final 分别指示排序过程中得到的有序序列中的第一个记录和最后一个记录在 d 中的位置。

希尔排序（重点）

原理：先将整个待排序的记录分割成若干子序列分别进行“直接插入排序”接插入排序。同一颜色进行排序，间隔最好奇次。

算法

void ShellInsert(SqList&Lintdk){(dk 为跨度，r[0]是暂存单元 j<=0，插入位置已找到)
for(i=dk+1;i<=L.length;++i){(控制要排序子表个数)
ifLT(L.r[i].key,L.r[i-dk].key) (L.ri 为待排序记录且小于)
L.r[0] = L.r[i]; (将 L.r[i]暂存到 L.r[0])
for(j=i-dk;j>0 &&LT(L.r[0].key,L.r[i].key);j - = dk)
L.r[j+dk]=L.r[i]; (将大于插入值的记录向后移动)
L.r[j+dk]=L.r[0]; (插入)
}
} ShellInsert
void ShellSort( SqList &L, int dita[], int t ) { (dita[0... t-1] 存放跨度
的数组)
for ( k = 0 ; k<t; ++ k)
ShellInsert(L, dita[k]);(由 dita[ k]得到跨度)
}ShellSort