Ringkasan
Gabungkan metode penyortiran adalah untuk menggabungkan dua (atau lebih dari dua) tabel yang dipesan ke dalam tabel yang dipesan baru, yaitu membagi urutan yang akan diurutkan menjadi beberapa setelah, masing -masing setelah dipesan. Kemudian yang dipesan berikutnya digabungkan ke dalam urutan yang dipesan secara keseluruhan.
Gabungan penyortiran diimplementasikan menggunakan rekursi, yang termasuk dalam "membagi dan menaklukkan". Array target dibagi menjadi dua dari tengah, dan kemudian kedua array diurutkan secara terpisah. Setelah penyortiran selesai, kedua array "digabungkan" bersama -sama. Hal terpenting dalam menggabungkan penyortiran adalah proses "gabungan". Dalam proses penggabungan, ruang tambahan yang konsisten dengan dua array yang perlu digabung diperlukan.
Gambar reproduksi:
melangkah
Terapkan ruang sehingga ukurannya adalah jumlah dari dua urutan yang diurutkan. Ruang ini digunakan untuk menyimpan urutan gabungan untuk mengatur dua pointer. Posisi awal adalah posisi awal dari dua urutan yang diurutkan, bandingkan elemen yang ditunjukkan oleh dua pointer, pilih elemen yang relatif kecil dan masukkan ke dalam ruang gabungan, dan pindahkan pointer ke posisi berikutnya. Ulangi langkah 3 sampai pointer mencapai ujung urutan. Salin semua elemen yang tersisa dari urutan lain langsung ke akhir urutan yang digabungkan.
Data mentah:
3 5 2 6 2
Prasyarat untuk penggabungan adalah untuk memisahkan array, membaginya menjadi dua, dan kemudian membaginya menjadi dua, dan mereka tidak dapat dibagi lagi, dan menggabungkan mereka.
Babak pertama dipisahkan, indeks 2 ((0+4)/2 = 2) adalah tengah
[3 5 2] [6 2]
Putaran pemisahan kedua, terpisah [3 5 2]
[3 5] [2] [6 2]
Babak ketiga pemisahan, terpisah [3 5]
[3] [5] [2] [6 2]
Gabungkan [3] [5]
[3 5] [2] [6 2]
Gabungkan [3 5] [2]
[2 3 5] [6 2]
Babak keempat dipisahkan, dipisahkan [6 2]
[2 3 5] [6] [2]
Gabungkan [6] [2]
[2 3 5] [2 6]
Gabungkan [2 3 5] [2 6]
[2 2 3 5 6]
Implementasi Kode (Java)
Paket com.coder4j.main.arithmetic.sorting; kelas publik gabungan {private static int mark = 0; / ** * Gabungkan Sort * * @param Array * @param Low * @param High * @return * / private static int [] sort (int [] array, int low, int high) {int mid = (rendah + tinggi) / 2; if (rendah <tinggi) {Mark ++; System.out.println ("Throwth In Progress" + Mark + "Pemisahan selanjutnya, GET"); System.out.println ("[" + rendah + "-" + mid + "] [" + (mid + 1) + "-" + tinggi + "]"); // Sortir Array Kiri (Array, Low, Mid); // Sortir array yang tepat (array, mid + 1, tinggi); // penggabungan kiri dan kanan (array, rendah, pertengahan, tinggi); } return array; } / ** * Gabungkan array * * @param array * @param low * @param mid * @param tinggi * / private static void gabungan (int [] array, int low, int mid, int high) {System.out.println ("gabungan:" + low + "-"); int [] temp = int baru [tinggi - rendah + 1]; int i = rendah; // pointer kiri int j = mid + 1; // right pointer int k = 0; // Pindahkan angka yang lebih kecil ke array baru pertama sementara (i <= mid && j <= tinggi) {if (array [i] <array [j]) {temp [k ++] = array [i ++]; } else {temp [k ++] = array [j ++]; }} // Mungkin ada elemen yang tersisa di salah satu dari dua array // pindahkan nomor yang tersisa di sebelah kiri ke array sementara (i <= mid) {temp [k ++] = array [i ++]; } // Pindahkan nomor yang tersisa di sebelah kanan ke array sementara (j <= tinggi) {temp [k ++] = array [j ++]; } // Timpa angka -angka dalam array array baru untuk (int m = 0; m <temp.length; m ++) {array [m+low] = temp [m]; }} / ** * Gabungkan Sort * * @param array * @return * / public static int [] sort (int [] array) {return sort (array, 0, array.length - 1); } public static void main (string [] args) {int [] array = {3, 5, 2, 6, 2}; int [] sorted = sort (array); System.out.println ("Hasil Akhir"); untuk (int i: diurutkan) {System.out.print (i + ""); }}}Hasil output tes:
The first separation is being performed, and the [0-2] [3-4] is being performed, and the second separation is being performed, and the [0-1] [2-2] is being performed, and the third separation is being performed, and the [0-0] [1-1] merge: [0-0] and [1-1] merge: [0-1] and [2-2] are being performed, and the fourth separation is being performed, and the [3-3] [4-4] Gabungkan: [3-3] dan [4-4] Gabungkan: [0-2] dan [3-4] Hasil akhir 2 2 3 5 6
Setelah pengujian, konsisten dengan hasil dalam contoh.