Python3希尔排序

苦叶子

发布于 2018-04-09 15:53:15

8160

发布于 2018-04-09 15:53:15

文章被收录于专栏：开源优测

希尔排序

概述

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

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

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

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

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

基本过程

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

排序过程：

先取一个正整数d1<n，把所有序号相隔d1的数组元素放一组，组内进行直接插入排序；
然后取d2<d1，重复上述分组和排序操作；
直至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)

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2018-01-24，如有侵权请联系 cloudcommunity@tencent.com 删除

python