直接插入排序

现将序列中的第一个记录看成一个有序子序列（标准），然后从第二个序列开始，逐个进行插入，直到整个序列有序，排序过程为n-1趟插入。

例

关键字序列 T=(13,6,3,31,9,27,5,11)

开始直接插入排序

第1趟：【13】,6,3,31,9,27,5,11
第2趟：【6,13】,3,31,9,27,5,11
第3趟：【3,6,13】,31,9,27,5,11
第4趟：【3,6,13,31】,9,27,5,11
第5趟：【3,6,9,13,31】,27,5,11
第6趟：【3,6,9,13,27,31】,5,11
第7趟：【3,5,6,9,13,27,31】,11
第8趟：【3,5,6,9,11,13,27,31】

时间复杂度

O(n²)

空间复杂度

O(1)

是否稳定性

稳定

应用场景

适用基本有序的情况

此时时间复杂度：O(n)

缺点

效率低

希尔（Shell）排序

先分组，对组内进行插入

先取一个正整数 d1，满足条件 d1<n ( n 序列长度)，把所有相隔 d1 的记录放一组，组内进行直接插入排序；然后取 d2，重复上述分组排序和操作;直至 di=1 ,即所有的记录放进一个组中排序为止。

提示： 一般取 d1=n/2，如果结果为偶数，则加 1

例子

例：T=(49,38,65,97,76,13,27,48,55,4)

第一趟希尔排序

n=10
d1=n/2=5

所以第一次排序应该把相隔 5 的数字放在一起比较

分组情况 :

• (49,13)
• (38,27)
• (65,48)
• (97,55)
• (76,4)

对个组进行 直接插入排序：

• (13,49)
• (27,38)
• (48,65)
• (55,97)
• (4,76)

再将各组归原位：

T=(13,27,48,55,4,49,38,65,97,76)

第二趟希尔排序

d1=5
d2=d1/2=5/2=2
因为是偶数，所以 2 + 1 = 3

对上次的结果：T=(13,27,48,55,4,49,38,65,97,76) 进行操作

所以第二次排序应该把相隔 3 的数字放在一起比较

分组情况:

• (13,55)
• (27,4)
• (48,49)
• (55,38)
• (4,65)
• (49,97)
• (38,76)

对个组进行 直接插入排序：

• (13,55)
• (4,27)
• (48,49)
• (38,55)
• (4,65)
• (49,97)
• (38,76)

再将各组归原位：

T=(13,4,48,38,27,49,55,65,97,76)

第三趟希尔排序：

d2=3
d3=d2/2=3/2=1

对上次结果 T=(13,4,48,38,27,49,55,65,97,76) 进行操作

d3=1 的情况是整体是一组，所以直接进行直接插入排序

直接插入排序后：

T=(4,13,27,38,48,49,55,65,76,97)

时间复杂度

O(n²)

精确时间复杂度： O(n^2)

空间复杂度

O(1)

是否稳定

不稳定，因为跨 n 个元素取值

题

现需要对一个基本有序的数组进行排序。此时最适宜采用的算法为（）排序算法，时间复杂度为（）。

A、插入
B、快速
C、归并
D、堆

A、O(n)
B、O(nlgn)
C、0(n2)
D、O(n²lgn)

答案

A
A

参考：
https://blog.csdn.net/qq_43238568/article/details/130786315