插入排序

插入排序(Insertion Sort)

  1.     插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。

算法思路

  1. 从第一个元素开始，该元素可以认为已经被排序；
  2. 取出下一个元素，在已经排序的元素序列中从后向前扫描；
  3. 如果该元素（已排序）大于新元素，将该元素移到下一位置；
  4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
  5. 将新元素插入到该位置后；
  6. 重复步骤2~5。

动画演示

9.4 插入排序 - 图1

代码实现

  1. def IS(nums):
  2.     n = len(nums)
  3.     for i in range(1, n):       # 遍历每个元素
  4.         temp = nums[i]
  5.         j = i
  6.         while temp < nums[j-1] and j > 0:       # 寻找元素位置
  7.             nums[j] = nums[j-1]     # 将元素移到下一位置
  8.             j = j - 1
  9.         nums[j] = temp      # 将元素插入最终位置
  10.         # print(nums)     # 打印排序过程
  11.     return nums
  13. print(IS(nums=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]))
    运行结果

[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

    排序过程

[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]

[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
[3, 38, 44, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
[3, 5, 38, 44, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
[3, 5, 38, 44, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
[3, 5, 15, 38, 44, 47, 36, 26, 27, 2, 46, 4, 19, 50, 48]
[3, 5, 15, 36, 38, 44, 47, 26, 27, 2, 46, 4, 19, 50, 48]
[3, 5, 15, 26, 36, 38, 44, 47, 27, 2, 46, 4, 19, 50, 48]
[3, 5, 15, 26, 27, 36, 38, 44, 47, 2, 46, 4, 19, 50, 48]
[2, 3, 5, 15, 26, 27, 36, 38, 44, 47, 46, 4, 19, 50, 48]
[2, 3, 5, 15, 26, 27, 36, 38, 44, 46, 47, 4, 19, 50, 48]
[2, 3, 4, 5, 15, 26, 27, 36, 38, 44, 46, 47, 19, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

复杂度分析

    时间复杂度分析：插入排序的比对主要是寻找新项的插入位置，所以最好的情况是列表已经排好序，每趟只需比对一次，此时时间复杂度为O(n);最坏的情况是列表的顺序是逆序的，需要比对的次数与冒泡排序相同，也是

9.4 插入排序 - 图2%3D%5Cfrac%7Bn(n-1)%7D%7B2%7D%0A#card=math&code=%5Csum_%7Bi%3D1%7D%5E%7Bn-1%7D%7Bi%7D%3D1%2B2%2B%7B%5Ccdots%7D%2B%28n-1%29%3D%5Cfrac%7Bn%28n-1%29%7D%7B2%7D%0A)

次，此时的时间复杂度为O(n^2)。

    空间复杂度分析：插入排序只需要一个变量来存储取出元素的值，直到这个元素找到插入位置，该变量又去存储下一个元素的值。所以插入排序的空间复杂度为O(1)。

优缺点

    优点：插入排序是一个稳定算法，因为已经比较的两个相同的数的相对顺序是不会发生改变。对于较少的数据排序较快

    缺点：比较次数越少，移动次数越多。

性能改进

    在插入某个元素之前需要先确定该元素在有序数组中的位置，当数据量比较大的时候，这是一个很耗时间的过程。我们可以采用二分查找法改进，而不是逐个扫描，所以这种排序也被称为二分插入排序。