用Python实现排序算法——插入排序

    本文用python实现插入算法。插入算法的原理是:当前元素和已经排序好的部分比较,满足条件时插入,插入点之后的元素全部往后移。然而,我也正是受这个描述的误导,在实现的时候走了一些弯路。比如有以下列表:


test = [2, 5, 11, 21, 10, 18, 24]


比如当前元素是10,我在开最初的实现思路是从列表的第一个元素开始,一直比较到元素11才找到合适位置.这样做最终是可以实现排序的,但是有一个问题,就是当我把10插入11的位置之后,11和21都需要往后移,这又需要另一个循环,实现如下:


def insertSort(sort_list):
    list_length = len(sort_list)
    if list_length < 2 :
        return sort_list
    for i in range(1,list_length):
        key = sort_list[i]
        j = 0
        while j < i:
            if sort_list[j] > key:
                for k in range(i,j,-1):
                    sort_list[k] = sort_list[k-1]
                sort_list[j] = key
                break
            j += 1
    return sort_list

   首先,引入了三个循环变量以及三层循环,效率较低;其次是代码结构会比较混乱,需要改进。


   后来我想能不能比较完一个元素就把它移到合适的位置,好如去超市买水果,手里拿到不合适的,总会直接把它放到一边,不会再碰它。具体到算法实现,还用上面的列表举例,当前元素是10,先跟相邻的21比较,发现21比10大,则21往后移动一位,即移到10所在位置;然后10和11比较,又会把11往后移动一位;在比较到元素5时,发现已经找到了10应该存放的位置,而此时移动也随之完成。

代码实现如下:


def insertSort(sort_list):
    list_length = len(sort_list)
    if list_length < 2 :
        return sort_list
    for i in range(1,list_length):
        key = sort_list[i]
        j = i - 1
        while j >=0 and sort_list[j] > key:
            sort_list[j+1] = sort_list[j]
            j -= 1
        sort_list[j+1] = key
    return sort_list


   孰优孰劣,大家对比便知。

本文出自 “绵之学习笔记” 博客,请务必保留此出处http://chenmg.blog.51cto.com/3039876/1394505

用Python实现排序算法——插入排序,布布扣,bubuko.com

用Python实现排序算法——插入排序

上一篇:控制容器的宽高比---aspect-ratio


下一篇:plupload -- multiple file upload & Spring MVC