希爾排序的基本思想:
希爾排序是基於插入排序的改進,由於插入排序對於已排好的數列操作時是高效的,但插入排序一般是比較低效的,因為一次只能移動一位。所以希爾排序先透過分組排序,直到分組增量為1 。
例:
arr = [49,38,04,97,76,13,27,49,55,65],分組增量為5時,紅色數為一組,進行插入排序,依序循環
arr = [13,38,04,97,76,49,27,49,55,65],遍歷完成後,分組增加自減,
65 ,49,38,49,97,76],再繼續將分組增量為2的組別進行插入排序,直到分組增量為1
代碼:
Python代碼
def shell_sort(lists):
def shell_sort(lists): #希爾排序
count = len(lists)
step = 2
> 0: #透過group增量分組循環 for i in range(0, group): j = i + group k = j - group while k >= 0: #分組插入排序 if lists[k] > lists[k + group], lists[k] = lists[k], key k -= group += group group /= step return 化lists