首页 | 新闻 | 新品 | 文库 | 方案 | 视频 | 下载 | 商城 | 开发板 | 数据中心 | 座谈新版 | 培训 | 工具 | 博客 | 论坛 | 百科 | GEC | 活动 | 主题月 | 电子展
返回列表 回复 发帖

排序算法总结(python版)-3

排序算法总结(python版)-3

插入排序(Insertion Sort)

插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
算法描述

一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:

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

    def InsertSort(ls):
        for i in range(1,len(ls)):
            if ls[i-1] > ls[i]:
                tmp = ls[i]
                j = i-1
                while(j>=0 and ls[j] > tmp):
                    ls[j+1] = ls[j]
                    j -= 1
                ls[j+1] = tmp
            print(ls)
        return ls

插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。
返回列表