直接插入排序的简介
发布网友
发布时间：2022-04-23 02:06
共1个回答
热心网友
时间：2023-10-11 02:30
待排序记录 R1，R2，… ，Rn–1, Rn
第一步：R1
第二步：(R1 ), R2
第三步：(R1 , R2), R3
……
第 j 步：(R1，R2，… ，Rj–1), Rj
……
第 n 步: (R1，R2，… ，Rn–1), Rn．
例：j=5
原有序表中关键词比Rj大的记录数：dj
比较次数：dj+1 移动次数： dj+2 算法 InsertSort (R,n)
FOR j=2 TO n DO
( //每次将Rj插入到有序表R1，…，Rj–1中
K←Kj. R←Rj. i←j-1.
WHILE (i>0) AND (Ki>K) DO
(Ri+1←Ri.
i←i-1.)
Ri+1←R.
)
算法InsertSortA( R, s, e )
//引入虚拟记录,Ks-1≤min{Ki| s≤i≤e}
ISA1 [逐一排序]
FOR j=s+1 TO e DO
( i←j-1．K←Kj. R←Rj .
WHILE K<Ki DO
( Ri+1←Ri ．
i←i-1 ．)
Ri+1←R ．
)
ISA1 [逐一排序]
FOR j=s+1 TO e DO
( i←j-1．K←Kj . R←Rj .
WHILE K<Ki DO
( Ri+1←Ri ．i←i-l ) ．
Ri+1←R )
直接插入排序的时间复杂度为 O(n2)。 1．简单方法
首先在当前有序区R[1..i-1]中查找R[i]的正确插入位置k(1≤k≤i-1)；然后将R[k．．i-1]中的记录均后移一个位置，腾出k位置上的空间插入R[i]。
注意：若R[i]的关键字大于等于R[1．．i-1]中所有记录的关键字，则R[i]就是插入原位置。
2．改进的方法
一种查找比较操作和记录移动操作交替地进行的方法。具体做法：
将待插入记录R[i]的关键字从右向左依次与有序区中记录R[j](j=i-1，i-2，…，1)的关键字进行比较：
① 若R[j]的关键字大于R[i]的关键字，则将R[j]后移一个位置；
②若R[j]的关键字小于或等于R[i]的关键字，则查找过程结束，j+1即为R[i]的插入位置。
关键字比R[i]的关键字大的记录均已后移，所以j+1的位置已经腾空，只要将R[i]直接插入此位置即可完成一趟直接插入排序。
