Python插入排序算法

排序通常指把毫无规律的数据,按照一种特定的规律,整理成有序排列的状态。一般情况下,排序算法按照关键字的大小,以从小到大或从大到小的顺序将数据排列。

排序算法是最基础也是最重要的算法之一,在处理大量数据时,使用一个优秀的排序算法可以节省大量时间和空间。因为不同的排序算法拥有不同的特点,所以我们应根据情况选择合适的排序算法。

初级排序算法是指几种较为基础且容易理解的排序算法。初级排序算法包括插入排序、选择排序和冒泡排序 3 种。虽然它们的效率相对于高级排序算法偏低,但是在了解初级排序算法之后,再去学习相对复杂的高级排序算法会容易许多。本节教程我们介绍插入排序。

直观地讲,插入排序算法是把给定数组中的元素依次插入到一个新的数组中,最终得到一个完整的有序数组。之前我们已经讲过如何计算时间复杂度与空间复杂度,所以这里不再给出计算过程。插入排序的平均时间复杂度是 O(n2),最好情况下的时间复杂度是 O(n),最坏情况下的时间复杂度是 O(n2)。它的空间复杂度是 O(1)。

插入排序是一个稳定的排序算法。这里涉及一个新的概念:排序算法的稳定性。排序算法可以分为稳定的算法和不稳定的算法两类。在一个数组中,我们假设存在多个有相同关键字的元素。如果使用算法进行排序后,这些具有相同关键字的元素相对顺序一定保持不变,那么我们称这个排序算法为稳定的排序算法。

冒泡排序、插入排序和归并排序等都是稳定的排序算法。而不能保证这些元素排序前后的相对位置相同的算法,就是不稳定的排序算法。选择排序、希尔排序和快速排序等都是不稳定的排序算法。

直接插入排序的实现过程较为直观。排序开始时,对范例数组的每一个元素进行遍历。如图 1 所示,虚线的左侧表示已经有序的元素,右侧表示待排序的元素。
插入第一个元素
图 1:插入第一个元素

初始状态下,所有的元素都处于无序的状态,所以它们都在虚线的右侧。首先遍历的是第一个元素,这时候有序的数组为空(暂且把整个数组在虚线左侧的部分考虑成一个整体),所以第一个元素插入左侧的数组后必定是有序的。第一个元素插入完成后,接下来遍历的是整个数组中的第二个元素。

此时,我们就要考虑:如何使左侧有序的数组在新元素插入后保持有序?答案是再遍历一遍左侧有序的数组,找到正确的位置再插入新的元素。如图 2 所示,第二个元素 3 比有序数组中的 5 小,所以应该把它插入到 5 的左侧。
插入第二个元素
图 2:插入第二个元素

如图 3 所示,随后的过程是相似的。依次遍历无序数组中的元素,并把它们插入到有序数组中正确的位置。
插入排序完成
图 3:插入排序完成

当对无序数组的遍历完成后,有序数组中就包含了所有原始数组中的元素。这时候对原始数组的排序就完成了。

插入排序的代码再现了这个移动元素的过程。以下代码将数组 nums 正序排序。

插入排序代码:
nums = [5,3,6,4,1,2,8,7]
for i in range(1, len(nums)):   #遍历未排序的元素
    for j in range(i):       #遍历已有序的元素
        if nums[j]>nums[i]:      #找到插入位置
            ins = nums[i]
            nums.pop(i)
            nums.insert(j, ins)
            break           #完成插入后跳出for循环
print(nums)
运行程序,输出结果为:

[1,2,3,4,5,6,7,8]


代码中,第一个 for 循环用于遍历未排序元素。在上面的演示中,我们知道下标为 0 的元素,也就是第一个元素,已经处于有序状态,所以可以直接从第二个元素开始插入排序,使用 range(1, len(nums))。

第二个 for 循环用于遍历已排序的元素,也就是下标小于当前元素的所有元素,所以使用 range(i)。判断插入位置时,由于我们想把元素递增地排列,所以当前元素的插入位置应是在第一个大于它的数据之前。

因为找到比当前元素大的数据后,程序会立刻进行插入排序并跳出循环,从而可以确定已经遍历过的元素必定小于当前元素。如果所有有序的元素都小于当前元素,那么当前元素应当留在原来的位置上,不必再进行插入排序。