バブルソートと単一サイズの配列に関する問題の発生

バブルソート

バブル ソートは、コンピューター サイエンスの分野における比較的単純な並べ替えアルゴリズムです。

バブルソートアルゴリズムは次のように動作します: (後ろから前へ)

1. 隣接する要素を比較します。最初のものが 2 番目のものより大きい場合は、両方を交換します。
2. 隣接する要素の各ペアに対して、最初のペアから始めて最後のペアで終わるまで、同じことを行います。この時点では、最後の要素が最大の数値である必要があります。
3. 最後の要素を除くすべての要素に対して上記の手順を繰り返します。
4. 比較する数値のペアがなくなるまで、要素の数を減らしながら上記の手順を繰り返します。

l 2 つの隣接する要素を順番に比較し、逆順を削除します (逆順は数学的な概念であり、ペアで表示されます。たとえば、50 と 30 は逆順のペアです。いわゆる逆順の削除とは、大きい方が大きいことを意味します) 1 つは後ろに配置され、小さい方は前に配置されます)

。

l このようにして、一連の比較を行った後、最大の番号を持つペアが最後になります。

l 次に、新しいラウンドの比較を続行します。前のラウンド後の最大値は比較に参加しなくなりますこの方法では、このラウンドで比較に参加する値が 1 つ減ります。前のラウンドより、など、比較する値が 2 つだけ残るまで繰り返します!

これは 二重ループであり、外側の層はラウンド数を制御し、内側の層は各ラウンドの比較の数を制御します。

配列に n 個の要素がある場合、合計 n-1 回の比較が必要です。これは外側のループの数です。

別の知識ポイントを追加します:

list — 配列内の値を小さい値から大きい値へいくつかの変数に代入し、次に大きい値から小さい値へ値を代入します

私が書いたバブルソートについて話して、それについて私自身の理解に注釈を付けさせてください:

リーリー

効果:小さい配列から大きい配列までの配列の並べ替えを実現しました

大きいものから小さいものまで実装したい場合は、同じアルゴリズムであり、中間の数値の比較を通じてすべて交換されます。

次に、私がインタビューで遭遇した問題について話しましょう。配列を取得し、最初の配列を最大、2 番目の配列を最小、3 番目の配列を 2 番目に大きく、4 番目の配列を 2 番目に小さいものとします。 .. このように進めます。

その時は、あるらしいとしか思ってなかった

array_pop: 配列の最後のデータをポップします

array_shift: 配列の先頭からデータをポップします

配列を大きいものから小さいものに並べ替えた後、最初の配列をポップアップして最大の配列を取得し、最後の配列をポップアップして最小の配列を取得し、これら 2 つを組み合わせて最大の配列と最小の配列を取得し、続けて実行します。全部取るまでこのように取り出します。

戻ったらこれが実現可能かどうか試してみます

次に、私が試した方法について話します。

例:

それでは最初のステップ: まず、バブリングによって配列を大きいものから小さいものへと並べ替えます

2 番目のステップでは、最初 (最大) と最後 (最小) のポップアップを再帰によってまとめ、すべてが取り出されるまで取り出します。

効果:

これを行うためのより良い方法があります。ここで話しているのは、その時にたまたま思いついた方法です。気を悪くしないでください。