Python3希尔排序

希尔排序

概述

希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”(Diminshing Increment Sort),是直接插入排序算法的一种更高效的改进版本。

希尔排序是非稳定排序算法。

该方法因D.L.Shell于1959年提出而得名。

希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;

随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。

基本过程

希尔排序属于插入类排序,是将整个有序序列分割成若干小的子序列分别进行插入排序。

排序过程:

  1. 先取一个正整数d1<n,把所有序号相隔d1的数组元素放一组,组内进行直接插入排序;
  2. 然后取d2<d1,重复上述分组和排序操作;
  3. 直至di=1,即所有记录放进一个组中排序为止。

时间成本

希尔排序是按照不同步长对元素进行插入排序,当刚开始元素很无序的时候,步长最大,所以插入排序的元素个数很少,速度很快;

当元素基本有序了,步长很小,插入排序对于有序的序列效率很高。

所以,希尔排序的时间复杂度会比o(n^2)好一些。

代码

# -*- coding:utf-8 -*-

__author__ = "苦叶子"

import random

'''

公众号:开源优测

'''

# 随机生成1-10之间无序序列整数数据
def generator():
    random_data = []
    for i in range(0, 10):
        random_data.append(random.randint(1, 1000))

    return random_data

# 希尔排序
def shell_sort(data_list):
    # 序列长度
    length = len(data_list)
    # 步长,这个数据大家可以修改下,查看排序过程
    step = 2
    # 分组
    group = int(length / step)
    print("gourp: ", group)
    while group > 0:
        # 遍历分组,对所有分组进行排序
        for i in range(0, group):
            j = i + group            
            # 对分组进行排序
            while j < length:
                k = j - group
                key = data_list[j]
                while k >= 0:
                    if data_list[k] > key:
                        data_list[k + group] = data_list[k]
                        data_list[k] = key
                    k = k - group
                j = j + group

        group = int(group / step)    
        
    return data_list

if __name__ == "__main__":

    print("开源优测-积微速成计划基本功")

    # 生成随机无序数据
    random_data = generator()

    # 打印无序数据
    print(random_data)

    # 排序
    length = len(random_data)
    sorted_data = shell_sort(random_data)

    # 打印排序结果
    print(sorted_data)

原文发布于微信公众号 - 开源优测(DeepTest)

原文发表时间:2018-01-24

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏带你撸出一手好代码

Java元组的使用

元组在计算机领域有着特殊的意义,这个名字听起来似乎有些陌生, 平时在写代码也基本没什么应用场景, 然而, 出人意料的是, 元组跟程序设计密切相关, 可能有的同学...

5098
来自专栏苦逼的码农

从0打卡leetcode之day8--反转整数

假设我们的环境只能存储 32 位有符号整数,其数值范围是 [−231, 231 − 1]。根据这个假设,如果反转后的整数溢出,则返回 0。

1434
来自专栏移动端开发

swift 可选类型笔记

       晚上十一点半了,看书累了,原本想睡了的,想了想,还是把刚看的总结一下,把这篇笔记写了吧。广州下雨,真特么的冷。。好了,废话不说了,说正题说说Swi...

19610
来自专栏noteless

[五]java函数式编程归约reduce概念原理 stream reduce方法详解 reduce三个参数的reduce方法如何使用

java8 流相关的操作中,我们把它理解 "累加器",之所以加引号是因为他并不仅仅是加法

3133
来自专栏诸葛青云的专栏

一步一步教你从零开始写C语言链表——构建一个链表

今天小编给大家带来c语言难点--链表的讲解,一步一步教你从零开始写C语言链表---构建一个链表。

1360
来自专栏racaljk

C++11新语法糖之尾置返回类型

C++11的尾置返回类型初衷是为了方便复杂函数的声明和定义,但是当复杂度稍微提升一些的时候很明显能注意到这种设计的作用微乎其微.

1665
来自专栏带你撸出一手好代码

正则表达式「^」符号的正确理解方式

「^」这个符号在正则表达式的中的应用相信是所有程序员都掌握的, 因为它是正则表达式中最基础最常用的知识点。 它在正则表达式中表示两种不同的意义 01 表示匹配一...

2873
来自专栏Crossin的编程教室

【Python 第47课】 面向对象(1)

我们之前已经写了不少小程序,都是按照功能需求的顺序来设计程序。这种被称为“面向过程”的编程。 还有一种程序设计的方法,把数据和对数据的操作用一种叫做“对象”的...

2979
来自专栏技术小站

深入理解Java的接口和抽象类(转)

  对于面向对象编程来说,抽象是它的一大特征之一。在Java中,可以通过两种形式来体现OOP的抽象:接口和抽象类。这两者有太多相似的地方,又有太多不同的地方。很...

782
来自专栏架构师小秘圈

深入理解Java的接口和抽象类

架构技术干货第一时间送达! 对于面向对象编程来说,抽象是它的一大特征之一。在Java中,可以通过两种形式来体现OOP的抽象:接口和抽象类。这两者有太多相似的地方...

3405

扫码关注云+社区

领取腾讯云代金券