Python3 插入排序

淩亂°似流年 2023-06-11 03:29 11阅读 0赞

参考：菜鸟教程  [https://www.runoob.com/python3/python-insertion-sort.html][https_www.runoob.com_python3_python-insertion-sort.html]

$ 插入排序(Insertion Sort)

构建局部有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

【例】有一个推理小说书单，现在决定一本一本看，并按喜好度从高到低排序  
1.鸟人计划  
2.斜屋犯罪  
3.嫌疑人X的献身  
4.占星术杀人魔法  
5.十角馆事件  
6.钟表馆事件  
（如下蓝色部分表示有序部分）  
看了第一本，暂时放在第一位，1,2,3,4,5,6（接下来拿第2本和前面的比）  
看了第二本觉得更好看，2,1,3,4,5,6（接下来拿第3本和前面的比）  
看了第三本觉得比前面的都好看，3,2,1,4,5,6（接下来拿第4本和前面的比）  
看了第四本决定放于第三本之后，3,4,2,1,5,6（接下来拿第5本和前面的比）  
……(都好看，太南了，编不下去了……嫌疑人、占星术、钟表馆更看，剩下三本也不知如何排……)

$ 插入排序代码实现

def insertionSort(arr): 
      
        for i in range(1, len(arr)): 
      
            key = arr[i] 
            j = i-1  #j由i前一个索引开始（j的初值）,一直到左遇到一个arr[j]不比key小
            while j >=0 and key < arr[j] : 
                arr[j+1] = arr[j]   # key从i-1的位置开始和前面的数逐个比较，key小则“换位置”，
    #            arr[j] = key     #每次比较，key小则换到这个位置，不过由于还要继续比较，不用此时赋值
                j = j-1
            arr[j+1] = key      # 循环条件不满足，即比到头了arr[-1+1]=key;或key不比前面的数小，把key赋值给上一轮的位置
      
    #测试数组  
    arr = [12, 11, 13, 5, 6] 
    insertionSort(arr) 
    print ("排序后的数组:") 
    for i in range(len(arr)): 
        print ("%d" %arr[i])

[https_www.runoob.com_python3_python-insertion-sort.html]: https://www.runoob.com/python3/python-insertion-sort.html