[原]09-Python3实用教程-排序算法-插入排序

插入排序

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

最符合直观思维的排序算法。

对于一个长度为N的列表,排序步骤:

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

2、从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置。

代码实现:

def sort(list):
    for i in range(len(list)):
        preIndex = i - 1
        current = list[i]
        while preIndex >= 0 and list[preIndex] > current:
            list[preIndex+1] = list[preIndex]
            preIndex-=1
        list[preIndex+1] = current
    return list

seq_list = [1, 3, 5, 6, 8, 10, 3]

print(sort(seq_list))
#[1, 3, 3, 5, 6, 8, 10]
分享 提问
comments powered by Disqus