python算法-插入排序

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

一、算法步骤

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

二、代码实现

def insertionSort(arr):
    for i in range(len(arr)):
        preIndex = i-1
        print("外层下标-1：",preIndex)
        current = arr[i]
        print("外层current基准数：",current)
        print("外层对比数：",arr[preIndex])
        while preIndex >= 0 and arr[preIndex] > current:
            print("进入的arr[preIndex]对比数",arr[preIndex])
            print("进入的current，基准数",current)
            arr[preIndex+1] = arr[preIndex]
            preIndex-=1
            print("内部preIndex",preIndex)
            print("arr",arr)
        print("最外层preIndex：",preIndex)
        arr[preIndex+1] = current
        print("最外层arr",arr)
    return arr

arr = [3,44,2,7,67,57,21]
a = insertionSort(arr)
print(a)

打印结果

外层下标-1： -1
外层current基准数： 3
外层对比数： 21
最外层preIndex： -1
最外层arr [3, 44, 2, 7, 67, 57, 21]
外层下标-1： 0
外层current基准数： 44
外层对比数： 3
最外层preIndex： 0
最外层arr [3, 44, 2, 7, 67, 57, 21]
外层下标-1： 1
外层current基准数： 2
外层对比数： 44
进入的arr[preIndex]对比数 44
进入的current，基准数 2
内部preIndex 0
arr [3, 44, 44, 7, 67, 57, 21]
进入的arr[preIndex]对比数 3
进入的current，基准数 2
内部preIndex -1
arr [3, 3, 44, 7, 67, 57, 21]
最外层preIndex： -1
最外层arr [2, 3, 44, 7, 67, 57, 21]
外层下标-1： 2
外层current基准数： 7
外层对比数： 44
进入的arr[preIndex]对比数 44
进入的current，基准数 7
内部preIndex 1
arr [2, 3, 44, 44, 67, 57, 21]
最外层preIndex： 1
最外层arr [2, 3, 7, 44, 67, 57, 21]
外层下标-1： 3
外层current基准数： 67
外层对比数： 44
最外层preIndex： 3
最外层arr [2, 3, 7, 44, 67, 57, 21]
外层下标-1： 4
外层current基准数： 57
外层对比数： 67
进入的arr[preIndex]对比数 67
进入的current，基准数 57
内部preIndex 3
arr [2, 3, 7, 44, 67, 67, 21]
最外层preIndex： 3
最外层arr [2, 3, 7, 44, 57, 67, 21]
外层下标-1： 5
外层current基准数： 21
外层对比数： 67
进入的arr[preIndex]对比数 67
进入的current，基准数 21
内部preIndex 4
arr [2, 3, 7, 44, 57, 67, 67]
进入的arr[preIndex]对比数 57
进入的current，基准数 21
内部preIndex 3
arr [2, 3, 7, 44, 57, 57, 67]
进入的arr[preIndex]对比数 44
进入的current，基准数 21
内部preIndex 2
arr [2, 3, 7, 44, 44, 57, 67]
最外层preIndex： 2
最外层arr [2, 3, 7, 21, 44, 57, 67]
[2, 3, 7, 21, 44, 57, 67]