当前位置:天才代写 > Python代写 > python 算法之希尔排序-python基础

python 算法之希尔排序-python基础

2021-02-16 15:28 星期二 所属: Python代写 浏览:24

希尔排序

希尔排序,也称下降增加量快速排序算法,是插入排序的一种更高效率的改善版本号。但希尔排序是是非非平稳快速排序算法。

希尔排序是根据插入排序的下列二点特性而明确提出改善方式的:

插入排序在对基本上早已排好序的数据信息实际操作时,高效率,即能够做到线形排列的高效率;

但插入排序一般来说是低效能的,由于插入排序每一次只有将数据信息挪动一位;

希尔排序的基础观念是:先将全部待排列的纪录编码序列切分变成多个子序列各自开展立即插入排序,待全部编码序列中的纪录“基础井然有序”时,再对全体人员纪录开展先后立即插入排序。

优化算法流程

  1. 挑选一个增加量编码序列 t1,t2,……,tk,在其中 ti > tj, tk = 1;
  2. 按增加量编码序列数量 k,对编码序列开展 k 趟排列;
  3. 每趟排列,依据相匹配的增加量 ti,将待排编码序列切分成多个长短为 m 的子序列,各自对各子表开展立即插入排序。仅增加量因素为 1 时,全部编码序列做为一个表来解决,表长短即是全部编码序列的长短。

Python 编码完成

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

    关键字:

天才代写-代写联系方式