Insert Sort - 插入排序
问题
用Insert Sort对长度为的无序序列从小到大(升序)排序。
解法
将长度为的序列分为左右两个部分,已排序的和未排序的,其中。如图:
初始时。
对和进行如下操作:
function Insert(s, k, n):
let x = s[k+1]
for i = [0, k+1]
if i = 0 and x <= s[i]
break
if i > 0 and s[i-1] <= x <= s[i]
break
if i <= k
move s[i...k] to s[i+1...k+1]
let s[i] = x
(1) Insert函数第3-7行:遍历找出一个适合插入的位置。其中属于边界条件,只需判断即可;
(2) Insert函数第8-10行:若找到一个合适的插入位置则将其插入;若找不到()则说明比中所有元素都大,不需要移动。下次调用Insert函数时输入参数变成,就可以将现在的加入中;
上述操作如图:
运行一次Insert函数可以将最左边的元素插入到中合适的位置(长度减1,长度加1)。初始时长度为,长度为,只需重复调用次Insert函数即可完成排序:
function InsertSort(s, n):
for k = [0, n-2]
Insert(s, k, n)
例如下图中,部分为,部分为,最左边的首部元素,在部分中合适的插入位置为()。
将向右移动一位到,将原移动到,就完成了一次插入。
复杂度
与BubbleSort算法类似,该算法的时间复杂度为,空间复杂度为。