1. Deskripsi Algoritma
Pilih Penyortiran: Misalnya, dalam array panjang yang tidak berurutan N, melintasi data N dalam perjalanan pertama, cari tahu nilai terkecil dan pertukarannya dengan elemen pertama, perjalanan kedua melintasi data N-1 yang tersisa, temukan nilai terkecil dan pertukaran dengan elemen kedua ... N-1ST melakukan pemilihan yang tersisa, temukan nilai terkecil dan pertukarannya, N-1ST melakukan pemilihan.
5 data yang tidak dipesan berikut digunakan sebagai contoh:
56 12 80 91 20 (Proses seleksi perjalanan pertama hanya disempurnakan dalam artikel)
Perjalanan pertama: 12 56 80 91 20
Perjalanan ke -2: 12 20 80 91 56
Trip 3: 12 20 56 91 80
Perjalanan ke -4: 12 20 56 80 91
2. Analisis Algoritma
Kompleksitas Waktu Rata -rata: O (N2)
Kompleksitas ruang: O (1) (untuk indeks pertukaran dan catatan)
Stabilitas: tidak stabil (misalnya, [5] dan [3] pertama dipertukarkan pada perjalanan pertama urutan [5, 5, 3], menyebabkan 5 pertama bergerak di belakang 5 kedua)
3. Implementasi Algoritma
PUBLIK PUBLIK PUTRIONSORT {public static void main (string [] args) {int len = 15; int [] ary = int [len] baru; Acak acak = acak baru (); untuk (int j = 0; j <len; j ++) {ary [j] = random.nextInt (1000); } System.out.println ("------------------"); // ary = int baru [] {10,9,8,7,6,5,4,3,2,1}; // pertukaran tes // ary = int int [] {1,2,3,4,5,6,7,8,10,9}; // pertukaran uji untuk (int j = 0; j <ary.length; j ++) {System.out.print (ary [j]+""); } selectdesc (ary); Selectasc (ARY); }/ * * SELECT SORT: Descending */static void selectDesc (int [] ary) {int compareCount = 0; // Bandingkan kali int changeCount = 0; // Jumlah pertukaran int len = ary.length; int maxvalueIndex = -1; // Catat indeks nilai minimum setelah putaran perbandingan untuk (int i = 0; i <len - 1; i ++) {maxvaleueDex = i; // dari 0 untuk (int j = i+1; j <len; j ++) {if (ary [maxValueIndex] <ary [j]) {maxvaleIndex = j; // Rekam indeks yang lebih besar CompareCount ++; }} // System.out.println ("MinValeIndex ==" + MaxValueIndex); if (maxValueIndex! = i) {// Jika indeks berbeda dari catatan di sebelah kiri, pertukaran ary [i] = ary [maxvalueIndex]+(ary [maxvalueIndex] = ary [i]) * 0; // pertukaran satu langkah changeCount ++; }} System.out.println ("/n -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ; ARY [MinIndex]+(ARY [MinIndex] = ary [i]) * 0; System.out.println("/n---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- compareCount + ", number of exchanges" + changeCount); untuk (int j = 0; j <ary.length; j ++) {System.out.print (ary [j]+""); }}}Mencetak
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- -----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------