クラシックアルゴリズムの集計ソート
10502 ワード
集計アルゴリズム
集計アルゴリズムの核心は分而治之である.時間複雑度O(n logn)、比較的安定
アルゴリズムステップ
1.統合後のシーケンスを格納するための空間を開く.2つのポインタを設定し、開始位置はそれぞれ2つの並べ替えられたシーケンスの開始位置3にある.2つのポインタが表す要素を比較し、より小さい要素をマージスペースに入れ、ポインタを後ろに移動します.1つのポインタが末尾5に達するまで、手順3を繰り返す.別のシーケンスの残りの要素を連結シーケンスの末尾にコピー
ダイレクトコード
集計アルゴリズムの核心は分而治之である.時間複雑度O(n logn)、比較的安定
アルゴリズムステップ
1.統合後のシーケンスを格納するための空間を開く.2つのポインタを設定し、開始位置はそれぞれ2つの並べ替えられたシーケンスの開始位置3にある.2つのポインタが表す要素を比較し、より小さい要素をマージスペースに入れ、ポインタを後ろに移動します.1つのポインタが末尾5に達するまで、手順3を繰り返す.別のシーケンスの残りの要素を連結シーケンスの末尾にコピー
ダイレクトコード
public int[] sort(int[] sourceArray) {
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
if (arr.length < 2) {
return arr;
}
// ,
int middle = (int) Math.floor(arr.length / 2);
int[] left = Arrays.copyOfRange(arr, 0, middle);
int[] right = Arrays.copyOfRange(arr, middle, arr.length);
// 、
return merge(sort(left), sort(right));
}
public int[] merge(int[] left, int[] right) {
int[] result = new int[left.length + right.length];// ,
int i = 0;
while (left.length > 0 && right.length > 0) {
if (left[0] <= right[0]) {
result[i++] = left[0];
left = Arrays.copyOfRange(left, 1, left.length);// , left
} else {
result[i++] = right[0];
right = Arrays.copyOfRange(right, 1, right.length);// , right
}
}
while (left.length > 0) {
result[i++] = left[0];
left = Arrays.copyOfRange(left, 1, left.length);
}
while (right.length > 0) {
result[i++] = right[0];
right = Arrays.copyOfRange(right, 1, right.length);
}
return result;
}