ソートアルゴリズムの実行時間:ソートアルゴリズムが異なるランダム入力で基本動作する回数(すなわち比較と交換が必要でなければアクセス配列を比較する回数)を計算する.
ソートアルゴリズムメモリオーバーヘッド:その場ソートアルゴリズム:関数呼び出しに必要なスタックと固定数の実力変数を除いて、追加のメモリオーバーヘッドを必要としない. その他のソートアルゴリズム:追加のメモリ領域に別のデータコピーを格納する必要がある
JavaでComparableインタフェースを継承し、comparareTo()で規定するソートルールを書き換えることで、カスタムデータ型オブジェクトのソート比較(p 155)を実現する.
基本ソートアルゴリズム選択ソート:残りの配列の中で最も値を選択し、交換して順番に並べ替えるの時間効率は、ソート回数に依存する.
N*N/2回比較:(N-1)+(N-2)+...+2+1 = N(N-1)/2 ~ N*N/2
N回交換運転時間は入力に関係なく、等長の順序乱数列並べ替え時間は同じである.
データ移動回数最小 挿入ソート:a[1]から、項目ごとにその前に隣接するソートデータと比較し、前方に隣接するデータがそれより小さいまで順番に交換して並べ替えるの並べ替え時間効率は、配列中の初期順序に依存する.
最大NN/2回比較、最小N-1回比較、平均NN/4回最大NN/2回交換、最低0回交換、平均NN/4回の交換回数は配列中の逆転個数と同じであり、比較回数は交換回数より小さくない、逆転個数より大きくないN-1 を加える.
部分秩序配列の並べ替えは非常に有効であるの改善方法:比較のたびに大きな要素を交換ではなく右に移動し、アクセス配列の回数をに半減する.
ヒルソート:迅速な挿入ソート、配列を最初に間隔h(h>N/3)で比較してサイズを交換し、各ラウンドのソートが完了すると、h=1(この場合、部分的に整列した配列の挿入ソート)まで新しいラウンドソートを行います. h小さいから大きいまでこれによって:1、4、13、40、121...h初期値は1であり、第1サイクル比較初期値はh*3+1であり、h
は挿入ソートよりも効率が高く、特に配列が大きい場合である.
運転時間がN*N級より小さい
コードの量は小さくて、余分なメモリの空間を必要としないで、アルゴリズムは比較的に簡単です 部分秩序配列:配列内の反転数が配列サイズの倍数より小さい場合.配列の各要素は、ソート後の最終位置から遠くない. 秩序化された大きな配列は、乱順の小さな配列の組合せを接続する.
配列にはいくつかの要素の位置が正しくないしかありません.