挿入ソートの基本的な考え方:
各ステップでは、ソート対象のレコードが、キー値のサイズに従って、すべてが挿入されるまで、以前にソートされたファイルの適切な位置に挿入されます。
例:
arr = [49,38,04,97,76,13,27,49,55,65]、2番目の数値をキー値として開始し、前の数値が大きい場合は前方比較し、 Exchange、
arr = [38,49,04,97,76,13,27,49,55,65] を実行し、3 番目の数値をキー値として使用し、前方比較し、前の数値と一致する場合は交換します。の方が大きいです、
arr = [38,04,49,97,76,13,27,49,55,65]、続行、arr = [04,38,49,97,76,13,27,49, 55,65]
注: 順番に前方比較する場合、前の配列は順序付けされているため、前の数値がキー値以下の場合、この前方比較ループから抜け出すことができ、アルゴリズムが大幅に改善されました。
コード:
def insert_sort(lists): #插入排序 count = len(lists) for i in range(1,count):#从第2个数起遍历 key = lists[i] j = i - 1 while j >= 0: if lists[j] > key: lists[j+1], lists[j] = lists[j], key else: break #当前一个数小于或等于key时,跳出循环 j -= 1 return lists