1

クイックソートのさまざまなバージョンをすべて説明するための完全な技術語彙を知っている人はいますか?

私が知っているのは「ファット ピボット」[A] (ピボットに一致するすべてのアイテムがサブ配列の中央に配置され、それ以上の並べ替えから除外される) です。

私が知りたいのは、1 つの要素 (ピボット) が中央に配置され、並べ替えから除外される場合 [B] と、中央にゼロ要素が配置される場合 [C] です。

これらのそれぞれの分割の例:
入力サブ配列は 5,3,2,9,5,7
[A] は [3,2],5,5,[ 9,7] を返します [
B]は [3,2] を返します],5,[9,5,7]
[C] は [3,2,5],[9,5,7] を与える

4

2 に答える 2

3

ええと、クイックソート？

クイックソートのバリエーションに関する情報を次に示します。

于 2009-02-21T23:55:10.927 に答える
0

さまざまな教科書で読んだ説明では、バリアントに共通の指定された名前はありません。それらは概要説明でラベル付けされており、正確なラベルはさまざまです。たとえば、あなたが言及した「ファット ピボット」は、「3 分割」、「3 ウェイ パーティション」、「オランダ フラグ アルゴリズム」と呼ばれることもあります。Robert Sedgewick が関与するさまざまな作品では、これらのうち少なくとも 2 つが使用されています。

于 2011-09-28T11:34:13.667 に答える