Pendahuluan: Topik Struktur Data Java dan Algoritma akan diperbarui dari waktu ke waktu. Pembaca dipersilakan untuk mengawasinya. Artikel ini dimulai dengan algoritma penyortiran paling sederhana - penyortiran bucket, dan menganalisis ide -ide implementasi, implementasi kode, karakteristik kinerja dan skenario penyortiran bucket yang berlaku.
0. Indeks algoritma penyortiran lainnya
//www.vevb.com/article/120879.htm
1. Ide penyortiran ember
Contoh sederhana:
Menyortir skor tes bahasa Inggris dari 6 orang (1 ~ 10 poin). If the score is [6, 5, 8, 8, 10, 9], the idea of sorting with buckets is to prepare 10 buckets, the numbers are 1~10 in sequence, and the scores are placed in the corresponding buckets, such as 6 points into the No. 6 bucket, and two 8 points into the No. 8 bucket... and then output them one by one according to the order of the bucket numbers (if there is, if there is, if there is no one, no output). Ini adalah ide dasar penyortiran ember.
Bahkan, ini hanya versi sederhana. Bayangkan saja, jika rentang rentang elemen yang akan diurutkan relatif besar, seperti 1 ~ 10.000, apakah Anda memerlukan 10.000 ember? Bahkan, dalam hal ini, satu elemen tidak selalu ditempatkan dalam ember, tetapi berkali -kali beberapa elemen ditempatkan dalam ember. Faktanya, daftar penyortiran dan hash asli memiliki prinsip yang sama.
Dalam penyortiran yang sebenarnya, elemen -elemen dalam setiap ember biasanya diurutkan menggunakan algoritma penyortiran lainnya, jadi lebih sering, penyortiran ember digunakan dalam kombinasi dengan algoritma penyortiran lainnya.
2. Kode penyortiran ember
Setelah menganalisis gagasan penyortiran ember, Anda harus terlebih dahulu mengetahui berbagai elemen yang akan diurutkan. Mengambil yang di atas sebagai contoh, nyatakan array dengan panjang 10 sebagai 10 ember, dan kemudian masukkan hasil satu per satu ke dalam ember, nilai ember adalah +1, dan akhirnya menghasilkan subskrip array dalam urutan terbalik. Nilai setiap posisi array adalah output beberapa kali, sehingga jenis ember dasar dapat dicapai.
bucketsort kelas publik {private int [] bucket; array int [] private; bucketsort publik (int range, int [] array) {this.buckets = int int [range] baru; this.array = array; } /*Penyortiran* / public void sort () {if (array! = Null && array.length> 1) {for (int i = 0; i <array.length; i ++) {buckets [array [i]] ++; }}}/*Penyortiran output*/public void sortout () {// Data output terbalik untuk (int i = buckets.length-1; i> = 0; i-) {for (int j = 0; j <buckets [i]; j ++) {System.out.print (i+"/t"); }}}}Kode Uji:
kelas publik sortest {public static void main (string [] args) {testbucketssort (); } private static void testbucketssort () {int [] array = {5,7,3,5,4,8,6,4,1,2}; Bucketsort bs = bucketsort baru (10, array); bs.sort (); bs.sortout (); // output print sort}}3. Karakteristik Kinerja Penyortiran Bucket
Penyortiran bucket sebenarnya hanya membutuhkan iterasi melalui semua elemen untuk diurutkan dan kemudian menempatkannya di posisi yang ditentukan secara berurutan. Jika waktu penyortiran output ditambahkan, semua ember perlu dilalui. Oleh karena itu, kompleksitas waktu penyortiran ember adalah O (n+m), n adalah jumlah elemen yang akan diurutkan, dan m adalah jumlah ember, yaitu, kisaran elemen yang akan diurutkan. Algoritma ini adalah algoritma penyortiran yang sangat cepat, tetapi kompleksitas spasial relatif besar.
Ketika kisaran ukuran elemen yang akan diatur relatif besar, tetapi jumlah elemen yang akan diatur relatif kecil, limbah luar angkasa lebih serius. Distribusi elemen yang akan diatur seragam setiap bulan, dan semakin tinggi tingkat pemanfaatan ruang, ini sebenarnya jarang.
Melalui analisis kinerja di atas, kita dapat memperoleh karakteristik penyortiran ember: cepat dan sederhana, tetapi pada saat yang sama, pemanfaatan ruang rendah. Ketika data yang akan diurutkan besar, tingkat pemanfaatan ruang tidak tertahankan.
4. Bucket Sorting Skenario yang berlaku
Menurut karakteristik penyortiran ember, penyortiran bucket umumnya berlaku untuk beberapa lingkungan tertentu, seperti rentang data relatif terbatas atau ada beberapa persyaratan spesifik, seperti kebutuhan untuk dengan cepat mendapatkan nilai -nilai tertentu melalui pemetaan hash, dan jumlah setiap angka yang perlu dihitung. Tetapi semua ini didasarkan pada mengkonfirmasi ruang lingkup data. Jika rentang lingkup terlalu besar, pertimbangkan untuk menggunakan algoritma lain.