Python シェルソート
Python3 例シェルソートは、減少増分ソートアルゴリズムとも呼ばれ、挿入ソートのより効率的な改良版です。ただし、シェルソートは不安定なソートアルゴリズムです。
シェルソートの基本思想は、まずソート対象のレコード全体のシーケンスをいくつかの部分シーケンスに分割し、それぞれ直接挿入ソートを行います。シーケンス全体のレコードが「ほぼ整列」になったら、全レコードに対して順に直接挿入ソートを行います。
例
def shellSort(arr):
n = len(arr)
gap = int(n/2)
while gap > 0:
for i in range(gap,n):
temp = arr[i]
j = i
while j >= gap and arr[j-gap] >temp:
arr[j] = arr[j-gap]
j -= gap
arr[j] = temp
gap = int(gap/2)
arr = [ 12, 34, 54, 2, 3]
n = len(arr)
print ("ソート前:")
for i in range(n):
print(arr[i]),
shellSort(arr)
print ("\nソート後:")
for i in range(n):
print(arr[i]),
上記のコードを実行すると、出力結果は次のとおりです：
排序前: 12 34 54 2 3 排序后: 2 3 12 34 54その他の拡張