希爾排序概述希爾排序(Shell's Sort)是插入排序的一種又稱“縮小增量排序”（Diminshing Increment Sort），是直接插入排序算法的一種更高效的改進版本,。 希爾排序是非穩(wěn)定排序算法,。 該方法因D.L.Shell于1959年提出而得名,。 希爾排序是把記錄按下標(biāo)的一定增量分組，對每組使用直接插入排序算法排序,； 隨著增量逐漸減少,，每組包含的關(guān)鍵詞越來越多，當(dāng)增量減至1時,，整個文件恰被分成一組,，算法便終止。 基本過程希爾排序?qū)儆诓迦腩惻判?是將整個有序序列分割成若干小的子序列分別進行插入排序,。 排序過程：
時間成本希爾排序是按照不同步長對元素進行插入排序，當(dāng)剛開始元素很無序的時候,，步長最大,，所以插入排序的元素個數(shù)很少，速度很快,； 當(dāng)元素基本有序了,，步長很小，插入排序?qū)τ谟行虻男蛄行屎芨摺?/p> 所以,，希爾排序的時間復(fù)雜度會比o(n^2)好一些,。 代碼# -*- coding：utf-8 -*-__author__ = "苦葉子" import random ''' 公眾號：開源優(yōu)測 ''' # 隨機生成1-10之間無序序列整數(shù)數(shù)據(jù) 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) # 步長，這個數(shù)據(jù)大家可以修改下,，查看排序過程 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("開源優(yōu)測-積微速成計劃基本功") # 生成隨機無序數(shù)據(jù) random_data = generator() # 打印無序數(shù)據(jù) print(random_data) # 排序 length = len(random_data) sorted_data = shell_sort(random_data) # 打印排序結(jié)果 print(sorted_data) |
|
|
