Apakah prinsip algoritma isihan gabungan dalam Java dan cara melaksanakannya

1. Idea asas

Isih gabungan ialah algoritma pengisihan yang berkesan berdasarkan operasi gabungan. Algoritma ini adalah aplikasi yang sangat tipikal menggunakan kaedah divide and conquer (Divide and Conquer). Gabungkan urutan yang telah diperintahkan untuk mendapatkan urutan yang tersusun sepenuhnya; iaitu, mula-mula membuat setiap urutan tersusun, dan kemudian membuat segmen seterusnya teratur. Jika dua senarai tertib digabungkan menjadi satu senarai tersusun, ia dipanggil gabungan 2 hala.

2. Analisis algoritma

1. Penerangan algoritma

Bahagikan urutan input panjang n kepada dua urutan panjang n/2 untuk kedua-dua urutan Cantuman ini digunakan masing-masing; dua urutan yang diisih digabungkan menjadi urutan pengisihan akhir.

2. Analisis Proses

(1), Sekarang kita akan membahagikan item [1] (indeks dari 0 hingga 0, kedua-dua belah termasuk) dan [28] indeks daripada 1 kepada 1, Kedua-dua belah pihak termasuk) digabungkan bersama.

(2), kerana 1 (belah kiri) <= 28 (belah kanan), kami menyalin {rightPart} ke dalam tatasusunan baharu.

(3 Oleh kerana belah kiri kosong, kami menyalin 28 (belah kanan) ke dalam tatasusunan baharu.

(4) Kami menyalin elemen dalam tatasusunan baharu kembali ke tatasusunan asal.

(5), kerana 3 (belah kiri) <= 21 (belah kanan), kami menyalin {rightPart} ke dalam tatasusunan baharu.

(6) Oleh kerana belah kiri kosong, kami menyalin 21 (belah kanan) ke dalam tatasusunan baharu.

(7), Sekarang kita akan membahagikan istilah [1,28] (indeks daripada 0 kepada 1, kedua-dua belah termasuk) dan [3,21] dengan indeks daripada 2 hingga 3, kedua-dua belah termasuk) digabungkan bersama.

(8), kerana 1 (belah kiri) <= 3 (belah kanan), kami menyalin {rightPart} ke dalam tatasusunan baharu.

(9), kerana 28 (belah kiri) > 3 (belah kanan), kami menyalin {rightPart} ke dalam tatasusunan baharu.

(10), kerana 28 (belah kiri) > 21 (belah kanan), kami menyalin {rightPart} ke dalam tatasusunan baharu.

(11 Oleh kerana belah kanan kosong, kami menyalin 28 (pecah kiri) ke dalam tatasusunan baharu.

(12 Kami menyalin elemen dalam tatasusunan baharu kembali ke tatasusunan asal.

(13), Sekarang kita akan membahagikan istilah [11] (indeks dari 4 hingga 4, kedua-dua belah termasuk) dan [7] dengan indeks dari 5 hingga 5, kedua-dua belah Semua termasuk) digabungkan bersama.

(14), kerana 11 (belah kiri) > 7 (belah kanan), kami menyalin {rightPart} ke dalam tatasusunan baharu.

(15), kerana pemisahan kanan kosong, kami menyalin 11 (pecahan kiri) ke dalam tatasusunan baharu.

(16 Kami menyalin elemen dalam tatasusunan baharu kembali ke tatasusunan asal.

(17), dan seterusnya

(18), kerana 1 (belah kiri) <= 6 (belah kanan), kita Salin { rightPart} ke dalam tatasusunan baharu.

(19), kerana 3 (belah kiri) <= 6 (belah kanan), kami menyalin {rightPart} ke dalam tatasusunan baharu.

(20), kerana 21 (belah kiri) > 6 (belah kanan), kami menyalin {rightPart} ke dalam tatasusunan baharu.

(21), kerana 21 (belah kiri) > 7 (belah kanan), kami menyalin {rightPart} ke dalam tatasusunan baharu.

(22), dan seterusnya, kami menyalin elemen dalam tatasusunan baharu kembali ke tatasusunan asal.

3. Demonstrasi GIF

3

Atas ialah kandungan terperinci Apakah prinsip algoritma isihan gabungan dalam Java dan cara melaksanakannya. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!