Artikel ini menjelaskan operasi pemilihan waktu linier yang diimplementasikan oleh Java berdasarkan algoritma partisi dan penaklukan. Bagikan untuk referensi Anda, sebagai berikut:
Masalah Pemilihan Waktu Linier: Diberikan N elemen dan bilangan bulat K, 1≤k≤n, perlu untuk mengetahui elemen terkecil dari elemen N ini (set linier yang diberikan di sini tidak teratur).
Seleksi linier yang dibagi secara acak
Metode Divisi Random Pemilihan Waktu Linear dapat meniru desain algoritma Sortir Cepat secara acak. Ide dasarnya adalah membagi array input secara rekursif. Tidak seperti penyortiran cepat, itu hanya memproses secara rekursif salah satu subarray yang terbagi.
Penjelasan Program: Gunakan fungsi acak untuk menghasilkan tolok ukur divisi, bagi array A [p: r] menjadi dua subarray A [p: i] dan [i+1: r], sehingga setiap elemen dalam [p: i] tidak lebih besar dari setiap elemen dalam [i+1: r]. Kemudian "j = i-p+1" menghitung jumlah elemen j dalam [p: i]. Jika k <= j, maka elemen terkecil k-th dalam [p: r] ada di sub-array a [p: i], dan jika k> j, elemen terkecil k-th ada di sub-array a [i+1: r]. Catatan: Karena diketahui bahwa elemen-elemen dalam sub-array A [p: i] semuanya lebih kecil dari elemen kecil K-th yang dapat ditemukan, elemen kecil K-th dalam [p: r] yang dapat ditemukan adalah elemen kecil K-th dalam [i+1: r].
Dalam kasus terburuk, misalnya: ketika elemen terkecil selalu ditemukan, selalu dibagi pada elemen terbesar, yang merupakan kompleksitas waktu O (n^2) . Namun, kompleksitas waktu rata -rata terkait secara linear dengan n, yaitu O (n)
Paket matematika; import java.util.scanner; import java.util.random; kelas publik acak -acakelect {public static void swap (int x, int y) {int temp = x; x = y; y = temp; } public int random (int x, int y) {acak acak = acak baru (); int num = random.nextInt (y)%(y - x + 1) + x; Return Num; } public int partition (int [] list, int low, int high) {int tmp = list [low]; // Array pertama adalah sumbu tengah sementara (rendah <tinggi) {while (low <high && list [high]> tmp) {high--; } Daftar [rendah] = Daftar [tinggi]; // Catatan yang lebih kecil dari sumbu tengah dipindahkan ke ujung bawah sementara (Low <High && List [Low] <tmp) {Low ++; } daftar [tinggi] = daftar [rendah]; // Catatan yang lebih besar dari sumbu tengah dipindahkan ke daftar high end} [rendah] = TMP; // Catatan yang lebih besar dari sumbu tengah dikembalikan rendah; // kembali ke posisi sumbu tengah} public int acakedPartition (int [] array, int kiri, int right) {int i = acak (kiri, kanan); swap (array [i], array [kiri]); Partisi kembali (array, kiri, kanan); } public int acakedSelect (int [] array, int kiri, int kanan, int k) {if (kiri == kanan) {return array [kiri]; } int i = ACOandPartition (Array, Left, Right); int j = i - kiri + 1; if (k <= j) {return acakedSelect (array, kiri, i, k); } else {return acakedSelect (array, i+1, kanan, kJ); }} public static void main (string args []) {System.out.println ("Hasil tes wulin.com:"); int [] a = {7,5,3,4,8,6,9,1,2}; untuk (int i = 0; i <9; i ++) {System.out.print (a [i]+""); } System.out.println (); RandomSelect r = new acakelect (); System.out.println ("Elemen terkecil apa yang ingin Anda minta dalam array?"); @SuppressWarnings ("Resource") Scanner SC = Pemindai Baru (System.in); int m = sc.nextInt (); int n = r.randomizedSelect (a, 0,8, m); System.out.println ("" Th "dalam array ini" + m + "Elemen terkecil adalah:" + n); }}Hasil Menjalankan:
Untuk informasi lebih lanjut tentang algoritma java, pembaca yang tertarik dengan situs ini dapat melihat topik: "struktur data java dan tutorial algoritma", "ringkasan tips node dom java", "ringkasan file operasi java dan direktori" dan "ringkasan tip operasi java cache" tips java "tips java" Tips "Java Cache Tips"
Saya harap artikel ini akan membantu pemrograman Java semua orang.