挿入ソートとは何ですか?

挿入ソートには単純な挿入ソートとヒル ソートの 2 種類があります。単純な挿入ソートの時間計算量は [O(N2) 安定ソート]、ヒル ソートの時間計算量は [およびインクリメンタル シーケンスです。選択してください。関連する、不安定な並べ替え]。

#挿入並べ替え

単純な挿入並べ替え

並べ替えるグループを配置します。シーケンスはソートされたシーケンスとアンソートされたシーケンスの 2 つの部分に分かれています。初期状態では、ソートされたシーケンスには最初の要素のみが含まれ、アンソートされたシーケンスの要素は最初の要素を除いて N-1 個の要素になります。その後、要素は存在しません。ソートされたシーケンス内の要素は、ソートされたシーケンスに 1 つずつ挿入されます。このようにして、N-1 回の挿入後、未ソート シーケンスの要素数が 0 になり、ソートが完了します。

時間計算量: O(N2) 安定したソート

ヒル ソート

ソート対象の要素の集合を一定間隔でいくつかの配列に分割し、それぞれ挿入ソートを実行します。最初に設定した「間隔」は大きく、ソートの各ラウンドで間隔は「間隔」が 1 になるまで徐々に減少します。つまり、最後のステップでは単純な挿入ソートが実行されます。

時間計算量: とインクリメント シーケンスの選択は不安定なソートに関連します

以上が挿入ソートとは何ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。