首页 > 编程语言 > 详细

使用python实现8大排序算法-希尔排序

时间:2015-10-15 02:07:31      阅读:334      评论:0      收藏:0      [点我收藏+]

希尔排序的基本思想:

希尔排序是基于插入排序的改进,由于插入排序对于已排好的数列操作时是高效的,但插入排序一般是比较低效的,因为一次只能移动一位。所以希尔排序先通过分组进行排序,直到分组增量为1 。

例:

? ? ? ?arr = [49,38,04,97,76,13,27,49,55,65],分组增量为5时,红色数为一组,进行插入排序,依次循环遍历

? ? ? ?arr =?[13,38,04,97,76,49,27,49,55,65],遍历完成后,分组增量自减,

? ? ? ?arr =?[13,27,04,55,65,49,38,49,97,76],再继续对分组增量为2的组进行插入排序,直到分组增量为1

代码:

def shell_sort(lists):
    #希尔排序
    count = len(lists)
    step = 2
    group = count / step
    while group > 0:  #通过group增量分组循环
        for i in range(0, group):
            j = i + group
            while j < count:  #分组中key值的索引,通过增量自增
                k = j - group
                key = lists[j]
                while k >= 0:  #分组中进行插入排序
                    if lists[k] > key:
                        lists[k + group], lists[k] = lists[k], key
                    else: break
                    k -= group
                j += group
        group /= step
    return lists

?

使用python实现8大排序算法-希尔排序

原文:http://wuqinwang.iteye.com/blog/2249138

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!