Isih Pantas dalam Java

Artikel berikut, Isih Pantas dalam Java, menyediakan garis besar untuk algoritma isihan pantas dalam java. Algoritma Isih Pantas adalah salah satu algoritma pengisihan yang cekap dan serupa dengan algoritma isihan gabungan. Ini adalah salah satu algoritma yang lazim digunakan untuk tujuan pengisihan masa nyata. Kerumitan masa kes terburuk bagi algoritma ini ialah O(n^2), kerumitan masa purata kes ialah O(n log n), dan kerumitan masa kes terbaik ialah O(n log n).

Kerumitan ruang jika O(n log n), di mana n ialah saiz input. Proses pengisihan melibatkan pembahagian input, lelaran rekursif dan menandakan elemen penting untuk setiap rekursi. Jenis pengisihan dalam algoritma ini melibatkan perbandingan elemen bersebelahan secara berulang.

Mulakan Kursus Pembangunan Perisian Percuma Anda

Pembangunan web, bahasa pengaturcaraan, ujian perisian & lain-lain

Seberapa Pantas Isih Berfungsi dalam Java?

Algoritma Isih Pantas boleh dilaksanakan dalam Java dengan membentuk kod pseudo dengan urutan langkah yang direka dan diikuti dengan cara yang cekap.

• Prinsip utama algoritma isihan pantas yang ia berfungsi adalah berdasarkan pendekatan bahagi dan takluk dan juga merupakan algoritma isihan yang cekap.
• Tatasusunan input dibahagikan kepada sub-tatasusunan, dan pembahagian adalah berdasarkan elemen pangsi, iaitu elemen pusat. Sub-tatasusunan pada kedua-dua belah elemen pangsi ialah kawasan utama di mana pengisihan sebenarnya berlaku.
• Elemen pangsi pusat ialah asas untuk membahagikan tatasusunan kepada dua sekatan di mana separuh kiri elemen tatasusunan adalah lebih kecil daripada elemen pangsi dan separuh kanan elemen tatasusunan lebih besar daripada elemen tatasusunan.
• Sebelum mempertimbangkan elemen pangsi, ia boleh menjadi sesiapa sahaja daripada elemen tatasusunan. Ini biasanya dianggap sebagai yang tengah atau yang pertama, atau yang terakhir untuk memudahkan pemahaman. Elemen pangsi boleh menjadi satu rawak daripada mana-mana elemen tatasusunan.
• Dalam contoh kami, elemen terakhir tatasusunan dianggap sebagai elemen pangsi, di mana pembahagian sub-tatasusunan bermula dari hujung kanan tatasusunan.
• Akhir sekali, elemen pangsi akan berada dalam kedudukan diisih sebenar selepas selesai proses pengisihan, di mana proses utama pengisihan terletak pada logik pembahagian algoritma pengisihan.
• Kecekapan algoritma bergantung pada saiz sub-tatasusunan dan cara ia seimbang. Lebih banyak sub-tatasusunan tidak seimbang, lebih banyak kerumitan masa, yang membawa kepada kerumitan kes terburuk.
• Pemilihan elemen pangsi secara rawak menghasilkan kerumitan masa terbaik dalam banyak kes dan bukannya memilih indeks permulaan, penghujung atau tengah tertentu sebagai elemen pangsi.

Contoh untuk Melaksanakan Isih Pantas dalam Java

Algoritma QuickSort telah dilaksanakan menggunakan bahasa pengaturcaraan Java seperti di bawah, dan kod output telah dipaparkan di bawah kod.

• Kod pada mulanya mengambil input menggunakan kaedah quickSortAlgo() dengan tatasusunan, indeks awal dan indeks akhir, iaitu panjang tatasusunan sebagai argumen.
• Selepas memanggil kaedah quickSortAlgo(), ia menyemak sama ada indeks awal kurang daripada indeks akhir dan kemudian memanggil kaedah arrayPartition() untuk mendapatkan nilai elemen pangsi.
• Elemen partition mengandungi logik untuk menyusun elemen yang lebih kecil dan lebih besar berdasarkan nilai elemen di sekeliling elemen pangsi.
• Selepas mendapat indeks elemen pangsi selepas pelaksanaan kaedah partition, kaedah quickSortAlgo() dipanggil dengan sendirinya secara rekursif sehingga semua sub-tatasusunan dipisahkan dan diisih sepenuhnya.
• Dalam logik partition, elemen terakhir ditetapkan sebagai elemen pangsi dan elemen pertama dibandingkan dengan elemen pangsi, iaitu elemen terakhir di mana elemen ditukar berdasarkan sama ada ia lebih kecil atau lebih besar.
• Proses rekursi ini berlaku sehingga semua elemen tatasusunan diasingkan dan diisih, dengan hasil akhir ialah tatasusunan tersusun gabungan.
• Elemen ditukar di dalam lelaran untuk gelung hanya sekiranya elemen itu kurang daripada atau sama dengan elemen pangsi.
• Selepas menyelesaikan proses lelaran, elemen terakhir ditukar, iaitu nilai elemen pangsi dialihkan ke sebelah kiri supaya partition baharu dibuat, dan proses yang sama berulang dalam bentuk rekursi, yang menghasilkan siri operasi pengisihan pada partition yang mungkin berbeza sebagai pembentukan sub-tatasusunan daripada elemen tatasusunan yang diberikan.
• Kod di bawah boleh dijalankan pada mana-mana IDE, dan output boleh disahkan dengan menukar nilai tatasusunan dalam main(). Kaedah utama digunakan hanya untuk tujuan mendapatkan output dalam konsol. Sebagai sebahagian daripada piawaian pengekodan Java, kaedah utama boleh dialih keluar di bawah dan objek boleh dibuat, dan kaedah di bawah boleh dipanggil dengan menjadikannya bukan statik.

Pelaksanaan Kod Algoritma Isih Pantas dalam Java

Berikut ialah pelaksanaan kod:

Kod:

/*
* Quick Sort algorithm - Divide & Conquer approach
*/
public class QuickSortAlgorithm {
public static void main(String[] args) {
int[] array = { 99, 31, 1, 3, 5, 561, 1, 342, 345, 454 };
quickSortAlgo(array, 0, array.length - 1);
for (int ar : array) {
System.out.print(ar + " ");
}
}
public static int arrayPartition(int[] array, int start, int end) {
int pivot = array[end];
int i = (start - 1);
for (int ele = start; ele < end; ele++) {
if (array[ele] <= pivot) {
i++;
int swap = array[i];
array[i] = array[ele];
array[ele] = swap;
}
}
// Swapping the elements
int swap = array[i + 1];
array[i + 1] = array[end];
array[end] = swap;
return i + 1;
}
public static void quickSortAlgo(int[] arrayTobeSorted, int start, int end) {
if (start < end) {
int pivot = arrayPartition(arrayTobeSorted, start, end);
quickSortAlgo(arrayTobeSorted, start, pivot - 1);
quickSortAlgo(arrayTobeSorted, pivot + 1, end);
}
}
}

Output:

Kesimpulan

Algoritma Isih Pantas adalah cekap tetapi tidak begitu stabil berbanding dengan teknik isihan lain. Kecekapan algoritma isihan cepat berkurangan sekiranya terdapat lebih banyak elemen berulang yang merupakan kelemahan. Kerumitan ruang dioptimumkan dalam algoritma isihan pantas ini.

Atas ialah kandungan terperinci Isih Pantas dalam Java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!