当前位置：网站首页>内部排序——插入排序

内部排序——插入排序

2022-07-07 12:33:00 【InfoQ】

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

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