アルゴリズムが安定しているかどうかはどうすればわかりますか? ...
また、このアルゴリズム Bucketsort は Mergesort、Quicksort、Bubblesort、および Insertionsort とどのように比較されますか?
1 に答える
1
一見すると、キューが FIFO であれば安定しているように見えます。しかし、クラスや他の宿題から、より確実な決定を下すのに役立つコンテキストがいくつかあると思います.
ウィキペディアから：
安定性 安定した並べ替えアルゴリズムは、等しいキーを持つレコードの相対的な順序を維持します。すべてのキーが異なる場合、この区別は必要ありません。しかし、等しいキーがある場合、同じキーを持つ 2 つのレコード (R と S としましょう) があり、元のリストで R が S の前に表示される場合は常に、R が常に S の前に表示される場合、並べ替えアルゴリズムは安定しています。ソートされたリスト。整数、またはより一般的には、要素全体がキーであるデータなど、等しい要素が区別できない場合、安定性は問題になりません。ただし、次の数値のペアが最初のコンポーネントでソートされると仮定します。
http://en.wikipedia.org/wiki/Sorting_algorithm#Stability
他のアルゴリズムと比較する限り。ウィキペディアには簡潔なエントリがあります。
http://en.wikipedia.org/wiki/Bucket_sort#Comparison_with_other_sorting_algorithms
于 2012-06-08T07:59:57.473 に答える