Javaのマージソート

すべてのプログラマーは、最初に将来の作業のスキーム/計画/アーキテクチャをよく考えなければなりません。そうしないと、すべてが混乱して完全に無秩序になってしまいます。他の投稿と同様に、最初に計画が必要です。始めましょう。

• 1) 初心者向けにマージソートのトピックを取り上げましょう。
• 2) アーキテクチャと今後の作業の計画を作成します。
• 3) 計画のすべての部分を検討して説明します。
• 4) 性能と品質をチェックしましょう。

• 2.1) マージソートとは何ですか。
• 2.2) 可能な署名の説明。
• 2.3) 例を挙げてください。
• 2.4) 例を使用して Java での実装を説明します。
• 2.5) 追加のもの。

Merge - Java でのマージソート

「分割統治」の原則を意味します。そのアイデアとその意味は何ですか？

1. 並べ替え中。

   配列が 1 つの要素に等しくなるまで、配列を複数の部分に分割します。1要素ごとにソートされます。

2. 合併。

   ソートされた要素をマージします。
   2 組のカードの原理に基づいています。2組のカードをその値を上にしてテーブルに置き、最も低いカードが3番目のカードの山に置かれます。最終的に、特定のデッキのカードがなくなった場合は、結果として得られるデッキにカードを 1 枚ずつ移動します。結果は、2 つのソートされた配列をマージし、1 つの新しいソートされた配列になります。

費やされる時間は O(n log2 n) です。並べ替えは非常に高速であると考えられます。 必要な場合は、アルゴリズムの複雑さについて簡単に説明します。 次のような関数がよく見られます。

Sort(A, p, q);
Merge(A, p, q, r);

これはほぼ同じことですが、インデックスにリンクされているだけです。それらの変数は次のとおりです。

A = Array = Массив
p, q, r = индексы для массива
p - начало первого массива
q - конец первого массива
q + 1 - начало второго массива
r - конец второго массива

これらの変数が記述されていない場合、そのような関数を自分で作成しようとする人は、自分が何を望んでいるのかわかりません。そして、それが何であるかを調べるには Google を検索する必要があります。おそらく、見つかるでしょう。並べ替えの例を見てみましょう。配列があり{6, 1, 3, 5, 2, 4, 7, 8}、その長さが 1 より大きい場合、それを 2 つの部分に分割し、左側の部分{6, 1, 3, 5}と右側の部分を取得します{2, 4, 7, 8}。長さが 1 より大きくなるまで、2 つの部分に分割する操作を続けます。その結果、長さが 1 要素の配列の束、つまり が得られます{6} {1} {3} {5} {2} {4} {7} {8}。Java での実装は次のようになります。

public int [] sortArray(int[] arrayA){ // sorting Массива который передается в функцию
        // проверяем не нулевой ли он?
        if (arrayA == null) {
            return null;
        }
        // проверяем не 1 ли элемент в массиве?
        if (arrayA.length < 2) {
            return arrayA; // возврат в рекурсию в строки ниже см комменты.
        }
        // копируем левую часть от начала до середины
        int [] arrayB = new int[arrayA.length / 2];
        System.arraycopy(arrayA, 0, arrayB, 0, arrayA.length / 2);

        // копируем правую часть от середины до конца массива, вычитаем из длины первую часть
        int [] arrayC = new int[arrayA.length - arrayA.length / 2];
        System.arraycopy(arrayA, arrayA.length / 2, arrayC, 0, arrayA.length - arrayA.length / 2);

        // рекурсией закидываем поделенные обе части обратно в наш метод, он будет крутится до тех пор,
        // пока не дойдет до 1 element в массиве, после чего вернется в строку и будет искать второй такой же,
        // точнее правую часть от него и опять вернет его назад
        arrayB = sortArray(arrayB); // левая часть возврат из рекурсии строкой return arrayA;
        arrayC = sortArray(arrayC); // правая часть возврат из рекурсии строкой return arrayA;

        // далее опять рекурсия возврата слияния двух отсортированных массивов
        return mergeArray(arrayB, arrayC);
    }

次に、これらの配列を 1 にマージする必要があります。これはどのように行われるのでしょうか? 各配列を複数回実行することを避けるために、各配列の位置インデックスを入力しましょう。次に、これら 2 つの配列の合計の長さに等しいループを 1 回実行します。最初の配列と 2 番目の配列を取得し、最初の要素を取得して、最初の配列の要素番号 1と2 番目の配列の要素番号 1を比較します。小さい方が結果の配列に配置されます。ここで重要なのは、最初の配列から要素を取得した場合、ループが通過すると、最初の配列の 2 番目の要素と 2 番目の配列の 1 番目の要素を参照する必要があるということです。これを行うには、最初の配列の場合と同様に、2 番目の配列のインデックスを +1 増やし、チェックするときにサイクル数からそれを減算する必要があります。なぜこれを行うのかは明らかですか? それとも何も明確ではありませんか？:-) たとえば、2 つの配列があります: {1}{4}{8}そして{3}{6}{7} 、ループがあります:

for (int i = 0; i < arrayA.length + arrayB.length; i++) {
	if (arrayA[i] < arrayB[i]) {
	arrayC[i] = arrayA[i];
	} else {
	arrayC[i] = arrayB[i];
	}
}

ループの最初のパスで、arrayC[1] = {1}この要素を最初の配列から取得したことがわかります。次に、2 番目のループを通過するときに、要素{4}と をすでに比較する必要があり{3}ますが、これを行うには、両方の配列の位置インデックスとオフセットを考慮する必要があり、そのためにそれらを入力します。

int positionA = 0, positionB = 0;
for (int i = 0; i < arrayA.length + arrayB.length; i++) {
	if (arrayA[i - positionA] < arrayB[i - positionB]) {
	arrayC[i] = arrayA[i - positionA];
	positionB++;
	} else {
	arrayC[i] = arrayB[i - positionB];
	positionA++;
	}
}

しかし、それだけではありません。一部の配列がより早く終了する可能性があることを考慮する必要があります。たとえば、3 つの配列があります。 最初の配列{1}{3}{5}は{6}{7}{9} 2 番目の配列が到着する前に終了します。これにはチェックを入れる必要があります。これで、原則としてマージ関数の準備が整います。

public int [] mergeArray(int [] arrayА, int [] arrayB) {

int [] arrayC = int[arrayA.length + arrayB.length];
int positionA = 0, positionB = 0;

for (int i = 0; i < arrayC.length; i++) {
	if (positionA == arrayA.length){
	arrayC[i] = arrayB[i - positionB];
	positionB++;
	} else if (positionB == arrayB.length) {
	arrayC[i] = arrayA[i - positionA];
	positionA++;
	} else if (arrayA[i - positionA] < arrayB[i - positionB]) {
	arrayC[i] = arrayA[i - positionA];
	positionB++;
	} else {
	arrayC[i] = arrayB[i - positionB];
	positionA++;
	}
}
return arrayC;

この並べ替えで最も難しいのは、再帰遷移の原理です。それらの。左辺を 2 で割り切れるまで再帰に投げ込み、それを元に戻します。言葉で言うと、非常に複雑でわかりにくいものですが、想像しようとすると、まだ明確になっていない場合、完全に混乱してしまいます。配列を考えてみましょう{2}{1}{4}{3}。最初のソート再帰は、それを 2 つの部分に分割し、要素2-1で関数を再度実行し、次に要素2と1で再度実行し、それらを順番に返すため、最初にマージ関数に入り、1-2が続きます。 out 、その後、再帰が戻って4-3 をマージにスローし、次に4と3 を返します。その後、マージは3-4を返します。その後、再帰が再びスピンバックして1-2と3-4がスローされます。が merge に含まれると、ソートされた配列が1-2-3-4として返されます。以上、並べ替えは 2 つの関数で構成されています。

sortArray(array); 			// кладем массив который нужно отсортировать
mergeArray(arrayA, arrayB); 	// кладем 2 массива которые нужно слить в один

何らかのメインを書き留めると、次のようなものになります。

public static void main(String[] args) {
        Merge testMerge = new Merge();
        int [] result = testMerge.sortArray(new int[]{2,3,1,4});

        for (int i = 0; i < result.length ; i++) {
            System.out.print(result[i] + " ");
        }
    }

私にとって、この分類は完全な失敗でした。質問は 100 万件ありましたが、答えはありませんでした。インターネット全体を調べ、読み直し、大量のビデオを見ましたが、いつものように、答えは自分で見つけただけでした。そして、どこにでも点滅するソリューションとは完全に異なるソリューションを書き始めたときのみ）しかし、最終的には他のすべてのソリューションと同様であることが判明しました）））並べ替えは実​​際には最も簡単で、主なことはそれを実際に対話的に表示することです。コツをつかめば、すべてがうまくいきます。ビデオを作成します)))) これまでのところ、これで十分です:マージ ソート マージ ソート 最も重要なことは、常に次から計画を立てることです。始まり。何かを始める前に、少し待って考えた方が良いでしょう。時間はかかるかもしれませんが、何度も書き直したり、松葉杖を考えたりするよりも、理解と解決策が見えてくるはずです。皆様、お時間をいただきありがとうございました、幸運とご機嫌をお祈りします。） 追伸：良いことも悪いことも含めた批判、質問は大歓迎です。)))