C++ は組み込みの std::sort にイントロソート (イントロスペクティブ ソート) を使用し、クイックソートで開始し、深さの制限に達するとヒープソートに切り替えることを読みました。
また、深さの制限は 2*log(2,N) であると想定されていることも読みました。
この値は純粋に実験的なものですか? それとも、その背後にいくつかの数学的理論がありますか?
質問する
2432 次
2 に答える
2
間隔（範囲または配列）がある場合、空の（または1つの要素）間隔になる前に間隔を半分に分割する必要がある回数は です。これはlog(2,N)単なる数学的な事実であり、それを処理できます必要に応じて簡単に。すべてがクイックソートで完全にうまくいく場合log(2,N)、同じ理由で再帰回数が必要です (また、各再帰レベルで、間隔のすべての値を処理する必要があり、O(N*log(2,N))アルゴリズム全体が複雑になります)。問題は、クイックソートがさらに多くの再帰を必要とする可能性があることです (ピボット値の選択で「不運」になり続けると、間隔が半分に分割されず、代わりに不均衡な方法で分割されます)。さらに悪いことに、クイックソートは N 回再帰することになり、
heap-sort at への切り替え2*log(2,N)は、深すぎる再帰数を検出するための、一般的に優れたヒューリスティックです。
技術的には、ヒープソートとクイックソートの経験的なパフォーマンスに基づいて、どの制限が最適かを判断できます。しかし、そのようなテストはアプリケーションに大きく依存します (何をソートするか? 要素をどのように比較するか? 要素のスワップはどれくらい安くなるか? など)。したがって、 のようなほとんどの万能型の実装は、 のようstd::sortな合理的な制限を選択するだけ2*log(2,N)です。
于 2013-08-15T05:01:19.253 に答える