Python を使用して 8 つの並べ替えアルゴリズムを実装する - クイック ソート

クイックソートの基本的な考え方:

1回のソートでソート対象のデータを2つの独立した部分に分割し、一方の部分のすべてのデータがもう一方の部分のすべてのデータよりも小さい場合、この方法を使用してソートします。データの 2 つの部分は個別に実行され、並べ替えプロセス全体を再帰的に実行できるため、データ全体が順序付けされます。

例:

arr = [49,38,04,97,76,13,27,49,55,65]、最初の桁49をキー値として設定し、キー値より小さい数値を次から見つけます。右から左へ、見つかった数値を最初の桁に割り当てます

arr = [27,38,04,97,76,13,27,49,55,65] から、最初の桁からキー値を見つけます。大きい数値の場合は、見つかった数値を右から左に最後に見つかった数値に割り当てます

arr = [27,38,04,97,76,13,97,49,55,65]、および次に、右から左へ、左から右へ、左=右になるまで進み、ループから抜け出し、キー値をインデックス値に割り当てます。最後に、両側のグループを再帰します。

コード:

def quick_sort(lists, left, right):
    #快速排序
    if left >= right:  #当递归调用的分组为1个数时返回列表
        return lists
    key = lists[left]  #保存key值，在一轮调用结束时，存到中间值
    low = left
    high = right  #供递归调用时使用
    while left < right:  #通过下面两个循环依次交替赋值并使key值两侧为大小分组
        while left < right and lists[right] >= key:  
            right -= 1
        lists[left] = lists[right]
        while left < right and lists[left] <= key:
            left += 1
        lists[right] = lists[left]
    lists[right] = key
    quick_sort(lists, low, left-1)  #对key值左侧进行排序分组
    quick_sort(lists, left+1, high)  #对key值右侧进行排序分组
    return lists