私はデータを処理するプログラムで作業しています。ただし、コードを効率的にしたいので、実行時間が配列の反転数に依存しないソートアルゴリズムが必要なので、昇順でソートできます。配列の順序は常に次のとおりです。
n = 配列のサイズ
リスト = (1,2,3,...,(n/2 -1), (n/2),(n/2 + 1),...3,2,1
配列の反転の合計が次のようになることはわかっています。
- (n/2 -1) + (n/2 -2) + (n/2 - 3) +...+ 1
これは対称配列の多くの反転であると思います。配列の順序が常にそのようなものであることを知っているので、O(n) 時間でそれらをソートするアルゴリズムが必要です。挿入ソートの複雑さは配列の反転数に依存することは知っていますが、配列の反転数が n に依存するかどうかはわかりません