Algoritma Pengisihan Pantas di Jawa

Isih cepat dalam java, juga dikenali sebagai isihan partition-exchange, ialah algoritma isihan bahagi dan takluk. Isih pantas ialah contoh algoritma yang baik yang paling baik menggunakan cache CPU kerana sifat pembahagian dan penaklukannya. Algoritma Quicksort ialah salah satu algoritma pengisihan yang paling banyak digunakan, terutamanya untuk mengisih senarai besar, dan kebanyakan bahasa pengaturcaraan telah melaksanakannya. Algoritma Quicksort membahagikan data asal kepada dua bahagian: diisih secara individu dan kemudian digabungkan untuk menghasilkan data yang diisih.

Mulakan Kursus Pembangunan Perisian Percuma Anda

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

Mari kita pertimbangkan bahawa tatasusunan {8, 6, 3, 4, 9, 2, 1, 7} perlu diisih menggunakan Isih Pantas.

Langkah untuk Melaksanakan Algoritma Isih Pantas

1. Pilih elemen yang dipanggil pangsi daripada tatasusunan. Secara amnya, elemen tengah dipilih sebagai pangsi. Mari kita ambil 4 sebagai pangsi.

2. Susun semula tatasusunan kepada dua bahagian supaya elemen yang kurang daripada pangsi datang sebelum pangsi dan elemen yang lebih besar daripada pangsi muncul selepas pangsi. Langkah-langkah berikut diikuti:

• Pilih elemen paling kiri, iaitu 8; memandangkan 4 ialah pangsi, dan 8 lebih daripada 4, 8 perlu dialihkan ke kanan 4; di sebelah kanan, kita tinggalkan 7 kerana ia lebih besar daripada 4 dan pilih 1 untuk bertukar dengan 8 maka selepas menukar tatasusunan menjadi: 1,6,3,4,9,2,8,7
• Pilih elemen kiri seterusnya, iaitu 6; kerana 4 ialah pangsi, dan 6 lebih daripada 4, 6 perlu dialihkan ke kanan 4; di sebelah kanan, kita tinggalkan 7,8 kerana ia lebih besar daripada 4 dan pilih 2 untuk bertukar dengan 6 maka selepas menukar tatasusunan menjadi: 1,2,3,4,9,6,8,7
• Kini memandangkan semua elemen di sebelah kiri pangsi adalah kurang daripada pangsi dan semua elemen di sebelah kanan pangsi adalah lebih besar daripada pangsi, kita selesai dengan 4 sebagai pangsi.

3. Gunakan langkah 1 dan 2 secara rekursif untuk sub-array kiri (tatasusunan dengan elemen kurang daripada pangsi) dan untuk sub-array kanan (tatasusunan dengan elemen lebih daripada pangsi). Jika tatasusunan mengandungi hanya satu atau sifar elemen, maka tatasusunan itu dianggap pelbagai.

Program untuk Melaksanakan Algoritma Isih Pantas

Berikut ialah program java untuk mengisih tatasusunan integer menggunakan algoritma isihan pantas.

Kod:

import java.lang.*;
import java.util.*;
public class Main {
private int array[];
private int length;
public void sort(int[] inputArrayArr) {
if (inputArrayArr == null || inputArrayArr.length == 0) {
return;
}
this.array = inputArrayArr;
length = inputArrayArr.length;
performQuickSort(0, length - 1);
}
private void performQuickSort(int lowerIndex, int higherIndex) {
int i = lowerIndex;
int j = higherIndex;
// calculate pivot number
// middle element taken as pivot
int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];
// Divide into two subarrays
while (i <= j) {
/**
* In each iteration, find an element from left side of the pivot which
* is greater than the pivot value, and also find an element
* From right side of the pivot which is less than the pivot value. Once the search
* is complete, we exchange both elements.
*/
while (array[i] < pivot) {
i++;
}
while (array[j] > pivot) {
j--;
}
if (i <= j) {
swapNumbers(i, j);
//move index to next position on both sides
i++;
j--;
}
}
// call performQuickSort() method recursively
if (lowerIndex < j)
performQuickSort(lowerIndex, j);
if (i < higherIndex)
performQuickSort(i, higherIndex);
}
private void swapNumbers(int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public static void main(String args[]){
Main quickSort = new Main();
int[] inputArray = {8,6,3,4,9,2,1,7};
quickSort.sort(inputArray);
System.out.println("Sorted Array " + Arrays.toString(inputArray));
}
}

Output:

Kelebihan Algoritma Isih Pantas

Berikut ialah kelebihan algoritma isihan pantas:

• Lokasi Rujukan Cemerlang: Lokasi rujukan ialah keupayaan pemproses untuk mengakses lokasi memori yang sama secara berulang dalam tempoh masa yang singkat. Isih pantas dalam java menyediakan lokasi Rujukan yang sangat baik disebabkan oleh bilangan cache yang sangat kecil, yang pada seni bina moden adalah penting untuk prestasi.
• Isih Pantas Boleh Disejajarkan: Setelah langkah awal membahagikan tatasusunan kepada kawasan yang lebih kecil selesai, semua subarray individu boleh diisih secara berasingan secara selari. Atas sebab ini, isihan pantas berprestasi lebih baik.

Analisis Kerumitan Susunan Pantas

Quicksort ialah algoritma pantas dan rekursif ekor yang berfungsi mengikut prinsip bahagi dan takluk. Berikut ialah analisis kerumitannya dalam Kes Terbaik, Purata dan Terburuk:

• Kerumitan Kes Terbaik: Jika tatasusunan atau senarai mengandungi n elemen, maka larian pertama memerlukan O (n). Sekarang Menyusun baki dua subarray mengambil masa 2*O (n/2). Ini menyimpulkan kerumitan O (n logn) dalam kes terbaik.
• Purata Kerumitan Kes: Purata kes isihan pantas ialah O (n log n).
• Kerumitan Kes Terburuk: Memilih yang pertama atau terakhir akan menyebabkan prestasi kes terburuk untuk data yang hampir diisih atau hampir terbalik. Isih pantas melakukan O (n^2) dalam kes yang paling teruk.

 Di Jawa, Arrays. Kaedah Isih () menggunakan algoritma isihan pantas untuk mengisih tatasusunan.

Atas ialah kandungan terperinci Algoritma Pengisihan Pantas di Jawa. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!