イントロソートはクイックソートで始まり、再帰の深さがソートされる要素の数に基づくレベルを超えると、ヒープソートに切り替わります。その数は何ですか？特定の範囲または制限値はありますか?
質問する
4708 次
2 に答える
8
イントロソートアルゴリズムがクイックソートからヒープソートに切り替わるポイントは、 depth_limitによって決定されます。
depth_limit = 2・⎣log2 （ l ） ⎦</ p>
ここで、 lはソートされるシーケンスの長さであるため、シーケンス全体に対してl = <em>nです。再帰呼び出しごとに、depth_limitは1ずつ減らされます。デプスリミットが0に達すると、クイックソートからヒープソートに切り替わります。
于 2012-06-24T07:13:44.750 に答える
2
ウィキペディアの紹介記事を読んでみました。それは言う
再帰の深さをカウントします。対数の深さを超えると、アルゴリズムはクイックソートからヒープソートに切り替わり、クイックソートの最悪の場合の結果を抑えます。
そして、イントロソートに関するマッサーの元の論文を通して。
イントロソートは、ヒープソートに切り替わる前に2 * log（2、N）の計算を実行するため、ヒープソートよりも遅いと言われています。
私の理解では、再帰の深さは2 * log（2、N）です。
N = 300の要素を並べ替える場合、2 * 8=16になります
于 2012-06-24T07:16:25.620 に答える