交換ソート - バブル ソート (バブル ソート)

交換ソートは主にソート対象のレコードのキーコードをペアで比較し、ソート対象のレコードのキーコードがソート要件に反する場合に交換します。まず、列を並べ替えるバブリング プロセスを見てみましょう。1

i=1; //最初のレコードからペアごとの比較を設定します

i≧jの場合、ワントリップバブリングは終了します。

r[i].keyとr[i+1].keyを比較し、r[i].key ≤ r[i+1].keyの場合は交換せず、r[i]の場合は⑤

へ.key>r[i+1].key, r[i]=r[i+1]; r[i+1]を変更します。 ]

i=i+1 を r[i+1] と交換し、次の 2 つのレコードのペアごとの比較を調整し、②

バブル ソート方法に切り替えます: n レコードのテーブルの場合、最初のバブルは A です。最大のキー コードを持つレコード r[n] を取得し、n-1 レコードのテーブルに対して 2 番目のバブルが実行され、最大のキー コードを持つレコード r[n-1] が取得されます。これを n 個のレコードが押されるまで繰り返します。キーコードで指定します。

【アルゴリズム10.6】


j=n; //n件のテーブルから開始

j

i=1; //バブリング1回、最初から設定開始レコード ペアごとの比較を実行します。

i≧j の場合、1 つのバブリング トリップが終了します。j=j-1; バブル テーブル内のレコード数は -1 です。②

に進み、r[i].key と比較します。 r[i+1 ].key、r[i].key≤r[i+1].keyの場合、交換なし、⑤へ

r[i].key>r[i+1].keyの場合, r[i] r[i+1]; r[i] と r[i+1] を交換します

i=i+1; 次の 2 つのレコードを調整してペアで比較します。 ④へ

【効率分析】

スペース効率：補助ユニットは1台のみ使用。

時間効率: j 個のレコードを持つテーブルに対して合計 n-1 回のバブリング操作が必要であり、j-1 個のキー コードの比較が必要です。

移動数:

最良の場合: 並べ替える列はすでに順序が整っており、移動する必要はありません

最悪の場合: 各比較後に 3 つの移動が必要です。もっと見る 交換ソート-バブルソート (Bubble Sort) 関連記事は、PHP 中国語 Web サイトに注目してください。