Isih gabungan dalam Java

Setiap pengaturcara pada mulanya mesti memikirkan skema/pelan/seni bina kerja masa hadapan, jika tidak, semuanya akan berakhir dalam keadaan huru-hara, dengan anarki yang lengkap. Seperti mana-mana siaran, anda pada mulanya memerlukan rancangan, mari mulakan.

• 1) Mari kita ambil topik Isih Gabung untuk pemula.
• 2) Kami akan membuat seni bina dan rancangan untuk kerja selanjutnya.
• 3) Kami akan menyelesaikan dan menerangkan semua bahagian rancangan.
• 4) Jom semak prestasi dan kualiti.

• 2.1) Apakah itu pengisihan Gabung.
• 2.2) Penerangan tentang kemungkinan tandatangan.
• 2.3) Berikan satu contoh.
• 2.4) Huraikan pelaksanaan di Jawa menggunakan contoh.
• 2.5) Apa-apa tambahan.

Gabung - gabungkan jenis dalam Java

Menyiratkan prinsip "bahagi dan takluk". Apakah idea dan maksudnya?

1. Menyusun.

   Kami membahagikan tatasusunan kepada bahagian sehingga ia sama dengan 1 elemen. Setiap 1 elemen diisih.

2. Penggabungan.

   Menggabungkan elemen yang diisih.
   Berdasarkan prinsip dua dek kad. Kami meletakkan 2 dek kad di atas meja dengan nilainya meningkat, dan kad yang paling rendah diletakkan dalam timbunan kad ketiga yang terhasil. Akhirnya, jika kita kehabisan kad dalam dek tertentu, kita mengalihkannya satu demi satu ke dek yang terhasil. Hasilnya akan menjadi gabungan dua tatasusunan yang diisih, satu tatasusunan baru yang diisih.

Masa yang dibelanjakan ialah O(n log2 n). Pengisihan dianggap agak pantas. Secara ringkas tentang kerumitan algoritma, jika sesiapa memerlukannya. Anda selalunya boleh melihat fungsi seperti:

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

Ini adalah perkara yang sama, hanya dipautkan kepada indeks. Pembolehubah di dalamnya ialah:

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

Jika pembolehubah ini tidak diterangkan, maka orang yang meminta untuk membuat fungsi sedemikian sendiri tidak tahu apa yang dia mahu. Dan anda perlu menjelajah Google untuk mengetahui apakah itu, anda mungkin akan menemuinya, mungkin. Mari kita berikan contoh pengisihan kami. Terdapat tatasusunan {6, 1, 3, 5, 2, 4, 7, 8}, jika panjangnya lebih besar daripada 1, maka kita bahagikannya kepada 2 bahagian dan dapatkan bahagian kiri {6, 1, 3, 5}dan bahagian kanan {2, 4, 7, 8}. Kami meneruskan tindakan membahagi kepada 2 bahagian sehingga panjangnya lebih besar daripada 1. Hasilnya, kami mendapat sekumpulan tatasusunan dengan panjang 1 elemen, iaitu: {6} {1} {3} {5} {2} {4} {7} {8}. Pelaksanaan di Java adalah seperti ini:

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);
    }

Seterusnya anda perlu menggabungkan tatasusunan ini menjadi 1. Bagaimanakah ini dilakukan? Untuk mengelakkan melalui setiap tatasusunan beberapa kali, mari masukkan indeks kedudukan untuk setiap tatasusunan. Kemudian kita akan melalui gelung sekali, sama dengan panjang jumlah kedua-dua tatasusunan ini. Ambil tatasusunan pertama dan tatasusunan kedua, dan ambil elemen pertama, bandingkan nombor elemen 1 dalam tatasusunan pertama dan nombor unsur 1 dalam tatasusunan kedua ? Yang lebih kecil diletakkan dalam tatasusunan yang terhasil. Adalah penting di sini bahawa jika kita mengambil elemen daripada tatasusunan pertama, maka apabila gelung itu berlalu, ia harus merujuk kepada elemen ke-2 tatasusunan pertama dan kepada elemen pertama tatasusunan kedua. Untuk melakukan ini, anda perlu meningkatkan indeks tatasusunan kedua sebanyak +1 dan, apabila menyemak, tolakkannya daripada nombor kitaran, begitu juga untuk tatasusunan pertama. Adakah jelas mengapa melakukan ini? Atau tiada yang jelas sama sekali? :-) Sebagai contoh, terdapat 2 tatasusunan: {1}{4}{8}dan {3}{6}{7} Dan terdapat gelung:

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

Pada laluan pertama gelung, ternyata arrayC[1] = {1}: kami mengambil elemen ini daripada tatasusunan pertama. Kemudian, apabila melalui gelung kedua, kita mesti sudah membandingkan elemen {4}dan {3}, tetapi untuk melakukan ini kita perlu mengambil kira indeks kedudukan dan mengimbangi kedua-dua tatasusunan, untuk ini kita masukkannya.

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++;
	}
}

Tetapi bukan itu sahaja, anda perlu mengambil kira bahawa beberapa tatasusunan mungkin berakhir lebih awal. Sebagai contoh, terdapat 3 tatasusunan: {1}{3}{5}dan {6}{7}{9} Tatasusunan pertama akan berakhir sebelum yang kedua tiba, untuk ini anda perlu memasukkan semakan dan, pada dasarnya, fungsi gabungan sudah sedia.

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;

Perkara yang paling sukar tentang pengisihan ini ialah prinsip peralihan rekursi. Itu. kita membuang sebelah kiri ke dalam rekursi sehingga ia boleh dibahagikan dengan 2, dan kemudian melepaskannya kembali, dalam kata-kata ia adalah sangat rumit dan mengelirukan, tetapi apabila anda cuba bayangkan, jika ia masih belum jelas, maka ia benar-benar huru-hara. Mari kita ambil tatasusunan: {2}{1}{4}{3}. Rekursi pengisihan pertama akan membahagikannya kepada 2 bahagian dan menjalankan fungsi sekali lagi dengan elemen 2-1 , kemudian sekali lagi dengan elemen 2 dan 1 , kembalikannya secara bergilir-gilir, jadi mereka akan masuk ke dalam fungsi gabungan dahulu, dan 1-2 akan datang keluar , maka rekursi akan kembali semula dan membuang 4-3 ke dalam gabungan , kemudian 4 dan 3 , selepas itu gabungan akan kembali 3-4 , dan hanya kemudian rekursi akan berehat semula dan 1-2 dan 3-4 akan menjadi termasuk dalam gabungan , dan tatasusunan yang diisih akan dikembalikan 1-2-3-4 . Nah, itu sahaja, pengisihan terdiri daripada dua fungsi.

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

Jika anda menulis beberapa jenis utama, anda akan mendapat sesuatu seperti:

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] + " ");
        }
    }

Bagi saya, penyisihan ini adalah kegagalan sepenuhnya, terdapat sejuta soalan, tetapi tiada jawapan, saya menggali seluruh Internet, membaca semula, menonton sekumpulan video, tetapi seperti biasa, saya hanya menemui jawapannya sendiri. Dan hanya apabila saya mula menulis penyelesaian yang sama sekali berbeza daripada yang berkelip di mana-mana) Tetapi pada akhirnya ia ternyata serupa dengan yang lain))) Pengisihan sebenarnya adalah yang paling mudah, perkara utama adalah untuk membentangkannya secara interaktif dalam tindakan, dan segala-galanya menjadi pada tempatnya jika anda memahaminya, saya akan membuat video)))) Setakat ini, itu sahaja yang saya cukup untuk: Merge sort Merge-sort Perkara yang paling penting ialah sentiasa membuat rancangan daripada permulaan. Lebih baik tunggu sebentar dan fikir sebelum mula melakukan sesuatu. Ia mungkin mengambil lebih banyak masa, tetapi pemahaman dan penyelesaian akan muncul daripada perlu menulis semula beberapa kali dan menghasilkan tongkat. Terima kasih semua untuk masa anda, semoga berjaya dan mood yang baik. ) PS: Kritikan, baik dan buruk, serta soalan amat dialu-alukan. )))