Pythonのクイックソート方法

この記事では主に Python で実装されたクイック ソート アルゴリズムを紹介し、Python クイック ソートの原理、実装方法、および関連する操作テクニックを例の形で分析します。必要な方は参考にしてください。この記事の例では、 Python で実装されたクイック ソート アルゴリズム。参考までに、詳細は次のとおりです。

クイックソートの基本的な考え方は、1 回のソート処理を通じて、ソート対象のデータを 2 つの独立した部分に分割することです。他の部分のすべてのデータよりも小さい場合、この方法を使用してデータの 2 つの部分をそれぞれすばやく並べ替えることができ、並べ替えプロセス全体を再帰的に実行できるため、データ全体が順序付けされたシーケンスになります。

たとえば、[6, 8, 1, 4, 3, 9] というシーケンスでは、基数として 6 を選択します。右から左にスキャンして基数 3 より小さい数値を探し、6 と 3 の位置を交換して [3, 8, 1, 4, 6, 9]、次に左から右にスキャンして数値を探します。基数より大きい 数値は 8 です。6 と 8 の位置を入れ替えます ([3, 6, 1, 4, 8, 9])。基数の左側の数値が基数より小さくなり、右側の数値が基数より大きくなるまで、上記のプロセスを繰り返します。次に、参照番号の左側と右側のシーケンスに対してそれぞれ上記の方法を再帰的に実行します。

実装コードは次のとおりです:

def parttion(v, left, right):
  key = v[left]
  low = left
  high = right
  while low < high:
    while (low < high) and (v[high] >= key):
      high -= 1
    v[low] = v[high]
    while (low < high) and (v[low] <= key):
      low += 1
    v[high] = v[low]
    v[low] = key
  return low
def quicksort(v, left, right):
  if left < right:
    p = parttion(v, left, right)
    quicksort(v, left, p-1)
    quicksort(v, p+1, right)
  return v
s = [6, 8, 1, 4, 3, 9, 5, 4, 11, 2, 2, 15, 6]
print("before sort:",s)
s1 = quicksort(s, left = 0, right = len(s) - 1)
print("after sort:",s1)

実行結果:

before sort: [6, 8, 1, 4, 3, 9, 5, 4, 11, 2, 2, 15, 6]
after sort: [1, 2, 2, 3, 4, 4, 5, 6, 6, 8, 9, 11, 15]

以上がPythonのクイックソート方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。