欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

python編程實現(xiàn)希爾排序

 更新時間:2017年04月13日 09:02:46   作者:前程明亮  
這篇文章主要介紹了python實現(xiàn)希爾排序,已編程實現(xiàn)的希爾排序,具有一定的參考價值,感興趣的小伙伴們可以參考一下

觀察一下”插入排序“:其實不難發(fā)現(xiàn)她有個缺點:

  如果當(dāng)數(shù)據(jù)是”5, 4, 3, 2, 1“的時候,此時我們將“無序塊”中的記錄插入到“有序塊”時,估計俺們要崩盤,每次插入都要移動位置,此時插入排序的效率可想而知。  

  shell根據(jù)這個弱點進行了算法改進,融入了一種叫做“縮小增量排序法”的思想,其實也蠻簡單的,不過有點注意的就是:

增量不是亂取,而是有規(guī)律可循的。

希爾排序時效分析很難,關(guān)鍵碼的比較次數(shù)與記錄移動次數(shù)依賴于增量因子序列d的選取,特定情況下可以準確估算出關(guān)鍵碼的比較次數(shù)和記錄的移動次數(shù)。目前還沒有人給出選取最好的增量因子序列的方法。增量因子序列可以有各種取法,有取奇數(shù)的,也有取質(zhì)數(shù)的,但需要注意:增量因子中除1 外沒有公因子,且最后一個增量因子必須為1。希爾排序方法是一個不穩(wěn)定的排序方法。

首先要明確一下增量的取法(這里圖片是copy別人博客的,增量是奇數(shù),我下面的編程用的是偶數(shù)):

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

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

      最后一直到: d=1; 

好,注意看圖了,第一趟的增量d1=5, 將10個待排記錄分為5個子序列,分別進行直接插入排序,結(jié)果為(13, 27, 49, 55, 04, 49, 38, 65, 97, 76)

第二趟的增量d2=3, 將10個待排記錄分為3個子序列,分別進行直接插入排序,結(jié)果為(13, 04, 49, 38, 27, 49, 55, 65, 97, 76)

第三趟的增量d3=1, 對整個序列進行直接插入排序,最后結(jié)果為(04, 13, 27, 38, 49, 49, 55, 65, 76, 97)

重點來了。當(dāng)增量減小到1時,此時序列已基本有序,希爾排序的最后一趟就是接近最好情況的直接插入排序。可將前面各趟的"宏觀"調(diào)整看成是最后一趟的預(yù)處理,比只做一次直接插入排序效率更高。

本人是學(xué)python的,今天用python實現(xiàn)了希爾排序。

def ShellInsetSort(array, len_array, dk): # 直接插入排序
 for i in range(dk, len_array): # 從下標為dk的數(shù)進行插入排序
 position = i
 current_val = array[position] # 要插入的數(shù)

 index = i
 j = int(index / dk) # index與dk的商
 index = index - j * dk

 # while True: # 找到第一個的下標,在增量為dk中,第一個的下標index必然 0<=index<dk
 # index = index - dk
 # if 0<=index and index <dk:
 # break


 # position>index,要插入的數(shù)的下標必須得大于第一個下標
 while position > index and current_val < array[position-dk]:
 array[position] = array[position-dk] # 往后移動
 position = position-dk
 else:
 array[position] = current_val



def ShellSort(array, len_array): # 希爾排序
 dk = int(len_array/2) # 增量
 while(dk >= 1):
 ShellInsetSort(array, len_array, dk)
 print(">>:",array)
 dk = int(dk/2)

if __name__ == "__main__":
 array = [49, 38, 65, 97, 76, 13, 27, 49, 55, 4]
 print(">:", array)
 ShellSort(array, len(array))

輸出:

>: [49, 38, 65, 97, 76, 13, 27, 49, 55, 4]
>>: [13, 27, 49, 55, 4, 49, 38, 65, 97, 76]
>>: [4, 27, 13, 49, 38, 55, 49, 65, 97, 76]
>>: [4, 13, 27, 38, 49, 49, 55, 65, 76, 97]

首先你得先會插入排序,不會你必然看不懂。 

插入排序,即是對上圖三個黃色框中的數(shù)進行插入排序。舉個例子:13,55,38,76

直接看55,55<13, 不用移動。接著看38,38<55,那么55后移,數(shù)據(jù)變?yōu)閇13,55,55,76],接著比較13<38, 那么38替換55,變成[13,38,55,76]。其它同理,略。

這里有個問題,比如第二個黃色框[27,4,65],4<27, 那27往后移,接著4就替換第一個,數(shù)據(jù)變成[4,27,65],但是計算機怎么知道4就是在第一個啊??

我的做法是,先找出[27,4,65]第一個數(shù)的下標,在這個例子中27的下標為1。當(dāng)要插入的數(shù)的下標大于第一個下標1時,才可以往后移,前一個數(shù)不可以往后移有兩種情況,一種是前面有數(shù)據(jù),且小于要插入的數(shù),那你只能插在它后面。另一種,很重要,當(dāng)要插入數(shù)比前面所有數(shù)都小時,那插入數(shù)肯定是放在第一個,此時要插入數(shù)的下標=第一個數(shù)的下標。(這段話,感覺初學(xué)者應(yīng)該不大懂……)

為了找到第一個數(shù)的下標,最開始想的是用循環(huán),一直到最前面:

while True: # 找到第一個的下標,在增量為dk中,第一個的下標index必然 0<=index<dk
 index = index - dk
 if 0<=index and index <dk:
 break

在Debug時,發(fā)現(xiàn)用循環(huán)太浪費時間了,特別是當(dāng)增量d=1時,直接插入排序為了插入列表最后一個數(shù),得循環(huán)減1,直到第一個數(shù)的下標,后來我學(xué)聰明了,用下面的方法:

j = int(index / dk) # index與dk的商
index = index - j * dk

時間復(fù)雜度:

希爾排序的時間復(fù)雜度是所取增量序列的函數(shù),尚難準確分析。有文獻指出,當(dāng)增量序列為d[k]=2^(t-k+1)時,希爾排序的時間復(fù)雜度為O(n^1.5), 其中t為排序趟數(shù)。

穩(wěn)定性: 不穩(wěn)定

希爾排序效果: 

 

參考資料: 編程是我自己實現(xiàn)的。建議Debug看看運行過程

c++中八大排序算法

視覺直觀感受若干常用排序算法

C#七大經(jīng)典排序算法系列(下)

1.非系統(tǒng)的學(xué)習(xí)也是在浪費時間 2.做一個會欣賞美,懂藝術(shù),會藝術(shù)的技術(shù)人

以上就是本文的全部內(nèi)容,希望對大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。

相關(guān)文章

  • python模塊與C和C++動態(tài)庫相互調(diào)用實現(xiàn)過程示例

    python模塊與C和C++動態(tài)庫相互調(diào)用實現(xiàn)過程示例

    這篇文章主要為大家介紹了python模塊與C和C++動態(tài)庫之間相互調(diào)用的實現(xiàn)過程示例,有需要的朋友可以借鑒參考下,希望能夠有所幫助
    2021-11-11
  • python遺傳算法之geatpy的深入理解

    python遺傳算法之geatpy的深入理解

    本文主要介紹了python遺傳算法之geatpy的深入理解,主要從geatpy中的各種數(shù)據(jù)結(jié)構(gòu)一步一步進行學(xué)習(xí),具有一定的參考價值,感興趣的可以了解一下
    2022-04-04
  • Python松散正則表達式用法分析

    Python松散正則表達式用法分析

    這篇文章主要介紹了Python松散正則表達式用法,較為詳細的分析了松散正則表達式的概念、功能與相關(guān)使用技巧,需要的朋友可以參考下
    2016-04-04
  • Python對象轉(zhuǎn)JSON字符串的方法

    Python對象轉(zhuǎn)JSON字符串的方法

    這篇文章主要介紹了Python對象轉(zhuǎn)JSON字符串的方法,涉及Python基于json模塊實現(xiàn)json轉(zhuǎn)換的實現(xiàn)技巧,非常簡便易懂,需要的朋友可以參考下
    2016-04-04
  • Python 詳解爬取并統(tǒng)計CSDN全站熱榜標題關(guān)鍵詞詞頻流程

    Python 詳解爬取并統(tǒng)計CSDN全站熱榜標題關(guān)鍵詞詞頻流程

    讀萬卷書不如行萬里路,只學(xué)書上的理論是遠遠不夠的,只有在實戰(zhàn)中才能獲得能力的提升,本篇文章手把手帶你用Python爬取CSDN全站綜合熱榜標題,順便統(tǒng)計關(guān)鍵詞詞頻,大家可以在過程中查缺補漏,提升水平
    2021-11-11
  • python使用requests庫爬取拉勾網(wǎng)招聘信息的實現(xiàn)

    python使用requests庫爬取拉勾網(wǎng)招聘信息的實現(xiàn)

    這篇文章主要介紹了python使用requests庫爬取拉勾網(wǎng)招聘信息的實現(xiàn),文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2020-11-11
  • python多線程案例之多任務(wù)copy文件完整實例

    python多線程案例之多任務(wù)copy文件完整實例

    這篇文章主要介紹了python多線程案例之多任務(wù)copy文件,結(jié)合完整實例形式分析了Python使用multiprocessing模塊實現(xiàn)基于多線程的文件拷貝相關(guān)操作技巧,需要的朋友可以參考下
    2019-10-10
  • Python如何爬取實時變化的WebSocket數(shù)據(jù)的方法

    Python如何爬取實時變化的WebSocket數(shù)據(jù)的方法

    這篇文章主要介紹了Python如何爬取實時變化的WebSocket數(shù)據(jù)的方法,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2019-03-03
  • python如何將空格分隔輸入兩個數(shù)

    python如何將空格分隔輸入兩個數(shù)

    這篇文章主要介紹了python如何將空格分隔輸入兩個數(shù)問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教
    2024-02-02
  • 簡述Python2與Python3的不同點

    簡述Python2與Python3的不同點

    在Python2和Python3中都提供print()方法來打印信息,但兩個版本間的print稍微有差異。下面通過本文給大家介紹Python2與Python3的不同點,需要的朋友參考下
    2018-01-01

最新評論