pythonの一般的なソートアルゴリズムの実装

一.高速ソートの実装
高速ソートアルゴリズムの核心思想は、ソートする配列を1つの基準値(一般的に配列を選択する第1の要素)に基づいて2つ(基準値より大きいものは右、基準値より小さいものは左)にすることである.その後、2組の再帰(基準値より小さいものと基準値より大きいものはそれぞれ2分ソートし、各グループが分割できないまで順次再帰する)を行い、2分法思想は多くのアルゴリズムに応用されている.例えば、数構造が1分2であるため、2分の時間複雑度はO(n*logn)である.pythonの高速ソートコードは、次のとおりです.

# _*_ coding:utf-8 _*_


def quick_sort(array, i, j):
    if i >= j:
        return array
    mid = array[i]
    low = i
    high = j

    while i < j:

        while i < j and array[j] >= mid:
            j -= 1
        array[i] = array[j]

        while i < j and array[i] <= mid:
            i += 1
        array[j] = array[i]

    array[j] = mid

    quick_sort(array, low, i-1)
    quick_sort(array, i+1, high)
    return array


if __name__ == '__main__':
    lists = [20, 14, 5, 58, 18, 36, 12, 42, 39]
    print("       ：")
    for i in lists:
        print(i, end=" ")
    print("
       ：")
    for i in quick_sort(lists, 0, len(lists) - 1):
        print(i, end=" ")

二.バブルソート
バブルソートの核心思想は隣接する2つの元素の大きさを比較することであり、隣接する2つの元素を比較し、それから大きな元素を後ろに置く(順方向ソート)、1ラウンドの比較が終わった後に最大の元素を最後の位置に置く.

# _*_ coding:utf-8 _*_


def bubble_sort(array):
    l = len(array)
    for i in range(l-1):
        for j in range(l-i-1):
            if array[j] >= array[j+1]:
                array[j+1], array[j] = array[j], array[j+1]
    return array


if __name__ == '__main__':
    lists = [20, 14, 5, 58, 18, 36, 12, 42, 39]
    print("       ：")
    for i in lists:
        print(i, end=" ")
    print("
       ：")
    for i in bubble_sort(lists):
        print(i, end=" ")

三.ソートの選択
ソートを選択する核心思想は、現在の要素とその要素の後のすべての要素の大きさを比較し、最小の要素を現在の位置に移動することです.

def select_sort(array):
    l = len(array)
    for i in range(l):
        for j in range(i+1, l):
            if array[j] < array[i]:
                array[i], array[j] = array[j], array[i]
    return array


if __name__ == '__main__':
    lists = [20, 14, 5, 58, 18, 36, 12, 42, 39]
    print("       ：")
    for i in lists:
        print(i, end=" ")
    print("
       ：")
    for i in select_sort(lists):
        print(i, end=" ")

四.ソートの挿入

def insert_sort(array):
    l = len(array)
    for i in range(1, l):
        for j in range(i, 0, -1):
            if array[j] <= array[j-1]:
                array[j-1], array[j] = array[j], array[j-1]
    return array


if __name__ == '__main__':
    lists = [20, 14, 5, 58, 18, 36, 12, 42, 39]
    print("       ：")
    for i in lists:
        print(i, end=" ")
    print("
       ：")
    for i in insert_sort(lists):
        print(i, end=" ")