实现希尔排序——Python 希尔排序算法程序流程图

off999 2024-12-26 15:54 49 浏览 0 评论

关于希尔排序

希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。

算法步骤：选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；按增量序列个数 k，对序列进行 k 趟排序；每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

代码

# 手动输入数列
def main():
    text = input("请输入整数数列，以空格隔开>>\n")
    type = int(input("升序排列请输入1，降序排列请输入2>>\n"))
    nums = text.split() #将字符串转为数组
    orderNums = shellSort(nums,type)
    print("排序后的数列：",orderNums)

def shellSort(nums,type):
    import math
    gap = 1
    while (gap < len(nums) / 3):
        gap = gap * 3 + 1
    while gap > 0:
        for i in range(gap, len(nums)):
            temp = nums[i]
            j = i - gap
            while j >= 0 and int(nums[j]) > int(temp):
                nums[j + gap] = nums[j]
                j -= gap
            nums[j + gap] = temp
        gap = math.floor(gap / 3)
    return nums

#运行主程序
main()

总结