Python を使用した配列の波形ソート-Python チュートリアル-php.cn

Python を使用した配列の波形ソート

王林

リリース： 2023-09-15 20:45:02

転載

746 人が閲覧しました

Python を使用した配列の波形ソート

この記事では、配列の波形を並べ替えるための Python プログラムを学習します。

ソートされていない入力配列があるとします。次に、入力配列を波形形式で並べ替えます。配列 'arr [0..n-1]' が arr [0] >= arr [1] = arr [3] = を満たす場合. ....、配列が波形にソートされます。

このタスクを実行するためのさまざまな方法を次に示します &miinus;

方法 1: 組み込みの sort() 関数を使用する

以下は、目的のタスクを実行するために従うべきアルゴリズム/手順です。

入力配列と配列の長さをパラメータとして受け取り、入力配列を波形で並べ替える関数を作成します。
sort() 関数 (リストを昇順/降順に並べ替える) を使用して、入力配列を昇順に並べ替えます。
for ループ
を使用して、配列の長さになるまで交互に走査します(ステップ=2)
len()
関数 (オブジェクト内の項目数を返す) を使用して、入力配列の長さを取得します。
sortingInWaveform()
関数を呼び出します。 for ループを使用します
配列のすべての要素を走査します
配列の現在の要素を出力します。
次のプログラムは、Python の組み込み sort() 関数を使用して波形内の入力配列を並べ替えます。 -
リーリー＃＃＃出力＃＃＃
実行すると、上記のプログラムは次の出力を生成します &miinus;

− O(nLogn).

ここでは、指定された配列は sort 関数を使用して並べ替えられています。通常、この関数の時間計算量は O(NlogN) です。

マージソート、ヒープソート

などの O(nLogn) ソートアルゴリズムを適用する場合、上記の方法の時間計算量は O(nLogn) です。

方法 2: ループを 1 つだけ使用するアルゴリズム (ステップ)

以下は、目的のタスクを実行するために従うべきアルゴリズム/手順です。

for ループ を使用して、引数として 0、配列の長さ、ステップ値を渡して偶数のインデックス要素をすべて走査します。

if 条件付き

true の場合に要素を交換します。
if 条件文
を使用して、現在の偶数インデックス要素が次の要素より小さいかどうかを確認します。
true の場合に要素を交換します。
sortingInWaveform()
関数を呼び出します。
for ループ
配列/リストの対応する要素を出力します。
＃＃＃例＃＃＃
次のプログラムは、for ループを 1 つだけ使用し、組み込み関数を使用せずに入力配列を波形で並べ替えます。 − リーリー＃＃＃出力＃＃＃ 上記のプログラムを実行すると、次の出力が生成されます -
リーリー
時間計算量
- O(n)。ここでは、sort 関数を使用しませんでした。代わりに、for ループを使用して、平均して O(N) 時間の計算量を持つ、指定された配列の要素を反復処理しました。＃＃＃結論は＃＃＃
この記事では、2 つの異なる方法を使用して、指定された波形の配列を並べ替える方法を学びました。最初の方法と比較して時間計算量が O(log N) 削減された新しいロジックを使用しました。多くの場合、この種のアルゴリズムは時間の複雑さを軽減し、効率的なソリューションを実装するのに役立ちます。

以上がPython を使用した配列の波形ソートの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。