5.9.插入排序
Last updated
Last updated
插入排序,尽管仍然是 O(n^2 ),工作方式略有不同。它始终在列表的较低位置维护一个排序的子列表。然后将每个新项 “插入” 回先前的子列表,使得排序的子列表称为较大的一个项。Figure 4 展示了插入排序过程。 阴影项表示算法进行每次遍历时的有序子列表。
Figure 4
我们开始假设有一个项(位置 0 )的列表已经被排序。在每次遍历时,对于每个项 1至 n-1,将针对已经排序的子列表中的项检查当前项。当我们回顾已经排序的子列表时,我们将那些更大的项移动到右边。 当我们到达较小的项或子列表的末尾时,可以插入当前项。
Figure 5 详细展示了第五次遍历。在该算法中的这一点,存在由 17,26,54,77
和 93
组成的五个项的排序子列表。我们插入 31
到已经排序的项。第一次与 93 比较导致 93 向右移位。 77 和 54 也移位。 当遇到 26 时,移动过程停止,并且 31 被置于开放位置。现在我们有一个六个项的排序子列表。
Figure 5
insertSort
(ActiveCode 1)的实现展示了 存在 n-1 个遍历以对 n 个排序。从位置 1 开始迭代并移动位置到 n-1,因为这些是需要插回到排序子列表中的项。第 8 行执行移位操作,将值向上移动到列表中的一个位置,在其后插入。请记住,这不是像以前的算法中的完全交换。
插入排序的最大比较次数是 n-1 个整数的总和。同样,是 O(n^2 )。然而,在最好的情况下,每次通过只需要进行一次比较。这是已经排序的列表的情况。
关于移位和交换的一个注意事项也很重要。通常,移位操作只需要交换大约三分之一的处理工作,因为仅执行一次分配。在基准研究中,插入排序有非常好的性能。
ActiveCode 1