shell(希尔)排序

基本思想

由于插入排序在最坏的情况下时间复杂度为O(n的平方),在最好的情况下时间复杂度为O(n),如果对待排序元素按关键字基本有序,插入排序的效率将大大提高,显然当元素个数n较少时效率也比较高,shell排序就是从这两方面对插入排序进行改进的。

先将整个待排序序列分割成若干子序列,分别对各个子序列进行直接插入排序,等整个序列中的数据元素“基本有序”是,再对全体数据元素进行一次直接插入排序。


来自百度百科.png

python实现

#!/usr/bin/python
# encoding: utf-8

# 希尔排序
def shellSort(alist):
    # 设定步长
    step = len(alist) // 2
    while step > 0:
        # 对step到最后一个位置都进行插入排序
        for i in range(step, len(alist)):
            tmp = alist[i]
            j = i
            while j >= step and tmp < alist[j - step]:
                # 如果前面的数比tmp小,就往后移
                alist[j] = alist[j-step]
                # 每次都是按照step长度往前移动
                j -= step
            alist[j] = tmp
        # 更新步长
        step = step // 2


if __name__ == '__main__':
    a = [4, 1, 3, 7, 5, 2, 9, 6, 8,11,10]
    shellSort(a)
    print(a) #[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部...
    蚁前阅读 5,224评论 0 52
  • 概述:排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部...
    每天刷两次牙阅读 3,747评论 0 15
  • 排序的基本概念 在计算机程序开发过程中,经常需要一组数据元素(或记录)按某个关键字进行排序,排序完成的序列可用于快...
    Jack921阅读 1,467评论 1 4
  • 1.插入排序—直接插入排序(Straight Insertion Sort) 基本思想: 将一个记录插入到已排序好...
    依依玖玥阅读 1,286评论 0 2
  • 一、 单项选择题(共71题) 对n个元素的序列进行冒泡排序时,最少的比较次数是( )。A. n ...
    貝影阅读 9,264评论 0 10