Python を使用して 8 つのソート アルゴリズムを実装する - 挿入ソート

挿入ソートの基本的な考え方:

各ステップでは、ソート対象のレコードが、キー値のサイズに従って、すべてが挿入されるまで、以前にソートされたファイルの適切な位置に挿入されます。

例:

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]

注: 順番に前方比較する場合、前の配列は順序付けされているため、前の数値がキー値以下の場合、この前方比較ループから抜け出すことができ、アルゴリズムが大幅に改善されました。

コード:

Pythonコード

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