python希爾排序

希爾排序介紹

希爾排序(Shell Sort)是插入排序的一種。也稱縮小增量排序，是直接插入排序算法的一種更高效的改進版本,該方法的基本思想是：先将整個待排元素序列分割成若幹個子序列（由相隔某個“增量”的元素組成的）分别進行直接插入排序，然後依次縮減增量再進行排序，待整個序列中的元素基本有序（增量足夠小）時，再對全體元素進行一次直接插入排序。因為直接插入排序在元素基本有序的情況下（接近最好情況），效率是很高的，是以希爾排序在時間效率比直接插入排序有較大提高。

首先要明确一下增量的取法：

第一次增量的取法為： d=count/2;

第二次增量的取法為: d=(count/2)/2;

最後一直到: d=1;

看上圖觀測的現象為：

d=3時：将40跟50比，因50大，不交換。

将20跟30比，因30大，不交換。

将80跟60比，因60小，交換。

d=2時：将40跟60比，不交換，拿60跟30比交換，此時交換後的30又比前面的40小，又要将40和30交換，如上圖。

将20跟50比，不交換，繼續将50跟80比，不交換。

d=1時：這時就是前面講的插入排序了，不過此時的序列已經差不多有序了，是以給插入排序帶來了很大的性能提高。

代碼執行個體：

import time,random

#source = [8, 6, 4, 9, 7, 3, 2, -4, 0, -100, 99]
#source = [92, 77, 8,67, 6, 84, 55, 85, 43, 67]

source = [ random.randrange(10000+i) for i in range(10000)]
#print(source)



step = int(len(source)/2) #分組步長

t_start = time.time()


while step >0:
    print("---step ---", step)
    #對分組資料進行插入排序

    for index in range(0,len(source)):
        if index + step < len(source):
            current_val = source[index] #先記下來每次大循環走到的第幾個元素的值
            if current_val > source[index+step]: #switch
                source[index], source[index+step] = source[index+step], source[index]

    step = int(step/2)
else: #把基本排序好的資料再進行一次插入排序就好了
    for index in range(1, len(source)):
        current_val = source[index]  # 先記下來每次大循環走到的第幾個元素的值
        position = index

        while position > 0 and source[
                    position - 1] > current_val:  # 目前元素的左邊的緊靠的元素比它大,要把左邊的元素一個一個的往右移一位,給目前這個值插入到左邊挪一個位置出來
            source[position] = source[position - 1]  # 把左邊的一個元素往右移一位
            position -= 1  # 隻一次左移隻能把目前元素一個位置 ,還得繼續左移隻到此元素放到排序好的清單的适當位置 為止

        source[position] = current_val  # 已經找到了左邊排序好的清單裡不小于current_val的元素的位置,把current_val放在這裡
    print(source)

t_end = time.time() - t_start

print("cost:",t_end)