クイックソートは分割統治に基づくアルゴリズムです。その基本的な考え方は、大きな配列をベンチマーク番号に従って左と右の部分に分割することです。左の部分はベンチマークの番号より大きくなく、右の部分はベンチマークの番号より小さくありません。ベンチマーク数値。 次に、残りの番号が 2 つだけになるまで、2 つのコピーに個別にクイック ソートを適用します。

通常、クイック ソートは最も高速なソート アルゴリズムです。以下は Python で実装された例です。

#!/usr/bin/env python
# -*-coding: utf8 -*-

'''    
Quick sort

@author: シトウ
'''

from random import Random

def quick_sort(arr):
    if len(arr) > 1:
        qsort(arr, 0, len(arr) - 1)

def qsort(arr, start, end):
    base = arr[start]
    pl = start
    pr = end
    while pl < pr:
        while pl < pr and arr[pr] >= base:
            pr -= 1
        if pl == pr:
            break
        else:
            arr[pl], arr[pr] = arr[pr], arr[pl]

        while pl < pr and arr[pl] <= base:
            pl += 1
        if pl == pr:
            break
        else:
            arr[pl], arr[pr] = arr[pr], arr[pl]

    # now pl == pr
    if pl - 1 > start:
        qsort(arr, start, pl - 1)
    if pr + 1 < end:
        qsort(arr, pr + 1, end)

r = Random()
a = []
for i in range(20):
    a.append(r.randint(0, 100))

print a
quick_sort(a)
print a

クイックソートは不安定なソートですが、バブルソートは安定したソートです。

安定した並べ替えとは、並べ替え前に同じ数値が 2 つある場合 ([a=10、b=10、c=2] の並べ替えなど)、a と b が等しく、並べ替え前は a が b の前にあり、安定した後の結果が安定した並べ替えであることを意味します。ソートは [ c, a, b] ですが、a はまだ b の前にあり、不安定なソートでは 2 つの等しい数値の位置が交換されないことが保証されず、ソート結果が [c, b, a] になる可能性があります。