ソートアルゴリズム学習への道 - テーブル挿入ソート - JiYi Blog

テーブルの挿入ソートについては、「挿入ソート (概念)」で簡単に説明します。簡単にまとめて記事にしましたので、必要な方は参考にしてください。

テーブル挿入ソートは、その名前が示すように、インデックス テーブルを使用して元のテーブルを挿入ソートする利点は、元のテーブル内の要素を移動するプロセスを節約できることです。もちろん、単一の整数配列内の要素を移動するのは非常に便利ですが (実験目的のみ)、やや複雑な構造を持つテーブルの場合、テーブル内の要素を移動するのは実際には簡単ではありません。たとえば、(次の PHP の 2 次元配列)

$arr = array (

1=> array ( "uname"=>'张三','年齢'=>20,'occu'=>'PHP プログラマー'),

2=> array ( " uname"=>'李思','年齢'=>27,'occu'=>'PHP プログラマー'),

3=> array ( "uname "=>'赵五','年齢'=>19,'occu'=>'PHP プログラマー'),

4=> array ( "uname" =>'王六','年齢'=>33,'occu'=>'PHP プログラマー'),

5=> 配列 ( "uname"= >'Liu Da','age'=>35,'occu'=>'PHP プログラマー'),

6=> 配列 ( "uname"=> ;'公子经','年齢'=>29,'occu'=>'PHP プログラマー'),

7=> 配列 ( "uname"=> '公子小白','年齢'=>26,'occu'=>'PHP プログラマー'),

8=> array ("uname"=> 'Guan Zhong','age'=>80,'occu'=>'PHP プログラマー'),

9=> array ( "uname"=>' Kongqiu','age'=>76,'occu'=>'PHP プログラマー'),

10=> 配列 ( "uname"=>'Zengzi' ,'age'=>66,'occu'=>'PHP プログラマー'),

11=> 配列 (" uname"=>'zisi',' age'=>55,'occu'=>'PHP プログラマー'),

12=> array (" uname"=>'Zuo Qiuming','age '=>32,'occu'=>'PHP プログラマ'),

13=> 配列 ( "uname"=>'孟子','年齢'= >75,'occu'=>'PHP プログラマー'),

14=> array (" uname"=>'Song Xianggong','age'=> ;81,'occu'=>'PHP プログラマー'),

15=> 配列 (" uname"=>'秦牧公','age'=> 22,'occu'=>'PHP プログラマー'),

16=> array (" uname"=>'Chuzhuang の王','age'=> 45,'occu'=>'PHP プログラマ'),

17=> 配列 ( "uname"=>'Zhao Dun','age'=>58 ,'occu'=>'PHP プログラマー'),

18=> 配列 ( "uname"=>'Lian Po','age'=>18, 'occu'=>'PHP プログラマー'),

19=> 配列 ( "uname"=>'Lin Xiangru','age'=>39,' occu'=>'PHP プログラマー'),

20=> 配列 (" uname"=>'老子','age'=>100,'occu' =>'PHP プログラマー'),

);

この配列に対して、年齢をソートするだけで各要素の位置を変更したくない場合は、テーブル挿入ソートを使用できます。インデックス テーブルを使用して現在のテーブルを並べ替えます。

さて、テーブル挿入ソートの分析を始めます。まずインデックス テーブルが必要です。テーブル構造は次のとおりです (例として PHP を使用しています)

array (

Index=> array ( 'next '=>value)

)

index は、元のテーブル内の要素の次のインデックスであり、その次のインデックスを指します

たとえば、次の要素はソートする必要があります。

仮に添字が 1 から始まると考え、開始インデックスとして 0 が使用されます。並べ替え後のインデックス テーブル (テーブル B と呼ばれる) は次のようになります。

次に、この例に従って、このインデックス テーブルを段階的に構築します

ステップ 1:初期化 インデックス テーブルは、その 2 つの要素

を設定します。 ステップ 2: テーブル A を走査します。 現在、テーブル A の 2 番目の要素の値は 5 です。次に、インデックス テーブル (以降、B テーブルと呼びます) の 0 ビットの次の値から開始して、A[$next] と 5 のサイズを順に比較します。 B テーブルの走査を終了する条件は 2 つあります。 1 つは $next が 0 であり、もう 1 つは A[$next] が 5 以上でなければならないということです。

A[1] は 5 より大きいため、B[0] の次の値を変更します。

$next = B[0][next] 1 から開始

while ($next は 0 に等しくない){

if(A[ $next]<5)

$next = B[$next][next] このときの値$next の値は 0

If(A[$next]>=5)

ループから抜け出す

}

If($next = 0) //B テーブルの最後の要素まで、5 より大きい要素がまだないことを示し、その後、B[2] の次の値を次のように設定します。 0, B[1 の次の値] は 2 に設定され、その他は変更されません

If($next が 0 に等しくない) //A[$next] の値がより大きいことを示しますまたは 5 に等しい場合、 B[0][next] を 2 に設定し、B[2][next] を 1 に設定します

3 番目のステップは、A テーブルの現在の値を走査することです。 A テーブルの 3 番目の要素の 9 は 9 です。この手順は 2 番目の手順と同じなので、ここでは繰り返しません。 3 番目のステップの後、テーブル A と B は次のようになります。

B[3][next] = B[2][next]

B[2][next] = 3

ステップ 4: 2 番目のステップと同様に、A テーブルと B テーブルは次のとおりです

B[4][next] = B[2 ][next]

B[2][next] = 4

この時点で、インデックス テーブルの構築方法が導入されました。明確に紹介できたかわかりませんが、ご不明な点がございましたら、以下にメッセージを残していただければ、確認後できるだけ早く返信させていただきます。

以下では、PHP を使用してテーブル挿入ソートを実装します。テスト データは、記事の冒頭で 2 次元配列を使用します。

$link = array (); // リンクリスト

$link [0]= array ('next'=>1);// リンクリストを初期化 $link 最初の要素のみが使用されます先頭として

$link [1]= array ('next'=>0) //最初の要素を $link

/*

* 2 番目の要素から開始して配列の走査を開始します

*/

for ( $i =2; $i <= count ( $arr ); $i + +){

$p = $arr [ $i ]; // ソート対象の現在の要素を格納

$index =0;

$next = 1; // リンクされたリストを開始位置

から検索します while ( $next !=0){

if ( $arr [ $next ]['age']< $p [' age']){

$index = $next;

$next = $link [ $next ]['next']; > else ブレーク ; >

if ( $next == 0){

$link [ $i ]['next'] = 0;

$link [ $index ][ 'next'] = $i ;

}

else

{

$link [ $i ]['next']= $next ; $link [ $index ]['next']= $i ;

}

}

これでインデックス テーブルが構築されました。このインデックス テーブルを走査する限り、私たちが望む効果が得られます。以下は結果を出力するコードです

$next = $link [0]['next'];

while ( $next !=0){

print_r ( $arr [ $next ]);

$next = $link [ $next ]['next']

}

上記のコードから、テーブル挿入ソートの時間計算量が依然として O(n²)

であることがわかります。上記はすべてのテーブル挿入ソートの内容です。以下にメッセージを残してください。一緒に話し合って改善していきましょう。