跳转至

5.9.插入排序

5.9.插入排序

插入排序,尽管仍然是 $$O(n^2)$$,工作方式略有不同。它始终在列表的较低位置维护一个排序的子列表。然后将每个新项 “插入” 回先前的子列表,使得排序的子列表称为较大的一个项。Figure 4 展示了插入排序过程。 阴影项表示算法进行每次遍历时的有序子列表。

5.9.插入排序.figure4

Figure 4

我们开始假设有一个项(位置 0 )的列表已经被排序。在每次遍历时,对于每个项 1至 n-1,将针对已经排序的子列表中的项检查当前项。当我们回顾已经排序的子列表时,我们将那些更大的项移动到右边。 当我们到达较小的项或子列表的末尾时,可以插入当前项。

Figure 5 详细展示了第五次遍历。在该算法中的这一点,存在由 17,26,54,7793 组成的五个项的排序子列表。我们插入 31 到已经排序的项。第一次与 93 比较导致 93 向右移位。 77 和 54 也移位。 当遇到 26 时,移动过程停止,并且 31 被置于开放位置。现在我们有一个六个项的排序子列表。

5.9.插入排序.figure5

Figure 5

insertSort(ActiveCode 1)的实现展示了 存在 n-1 个遍历以对 n 个排序。从位置 1 开始迭代并移动位置到 n-1,因为这些是需要插回到排序子列表中的项。第 8 行执行移位操作,将值向上移动到列表中的一个位置,在其后插入。请记住,这不是像以前的算法中的完全交换。

插入排序的最大比较次数是 n-1 个整数的总和。同样,是 $$O(n^2)$$。然而,在最好的情况下,每次通过只需要进行一次比较。这是已经排序的列表的情况。

关于移位和交换的一个注意事项也很重要。通常,移位操作只需要交换大约三分之一的处理工作,因为仅执行一次分配。在基准研究中,插入排序有非常好的性能。

def insertionSort(alist):
   for index in range(1,len(alist)):

     currentvalue = alist[index]
     position = index

     while position>0 and alist[position-1]>currentvalue:
         alist[position]=alist[position-1]
         position = position-1

     alist[position]=currentvalue

alist = [54,26,93,17,77,31,44,55,20]
insertionSort(alist)
print(alist)

ActiveCode 1