ホームページ  >  記事  >  挿入ソートとは何ですか?

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

藏色散人
藏色散人オリジナル
2020-06-30 09:28:572947ブラウズ

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

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

#挿入並べ替え

単純な挿入並べ替え

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

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

ヒル ソート

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

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

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

声明:
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。