Penyortiran Pilihan Sederhana: (Pilih nilai minimum, letakkan terlebih dahulu, dan kemudian bit pertama bergerak mundur, jadi loop) Bit pertama dibandingkan dengan masing -masing setelah yang berikutnya, setiap kali bit terkecil di atasnya, dan bit pertama adalah mundur Promosikan (yaitu, digit pertama yang baru saja dipilih adalah nilai minimum, tidak lagi berpartisipasi dalam perbandingan, jumlah perbandingan dikurangi dengan 1)
Kompleksitas: Jumlah operasi yang diperlukan untuk melakukan pergerakan rekaman adalah 0--3 (N-1). / 2. Kompleksitas waktu total adalah O (N2);
Kompleksitas ruang o (1)
Peningkatan Algoritma: Setiap kali Anda membandingkan, itu adalah untuk menempatkan nilai terkecil di tempat pertama, sehingga Anda dapat membandingkannya dengan akhir, menemukan nilai minimum, dan meletakkannya langsung di tempat pertama, menghilangkan operasi switching dan pemindahan yang tidak berarti. Anda juga dapat mengubah arah, membandingkan bit terakhir dengan masing -masing yang sebelumnya, dan membuat nilai maksimum setiap kali, dan mendorong bit terakhir ke depan.
Kode Sumber Java:
Salinan kode adalah sebagai berikut:
public static void selectSort (date [] days) {
int min;
Temp Temp;
untuk (int i = 0; i <days.length; i ++) {
min = i;
untuk (int j = min+1; j <days.length; j ++) {
if (days [min] .compare (hari [j])> 0) {
min = j;
}
}
if (min! = i) {
temp = hari [i];
hari [i] = hari [min];
hari [min] = temp;
}
}
}
Tanggal kelas {
tahun int, bulan, hari;
Tanggal (int y, int m, int d) {
tahun = y;
bulan = m;
hari = D;
}
Public int Compare (tanggal tanggal) {
Kembali Tahun> Tanggal
: Bulan> Date.month?
: Day> Date.day?
}
public void print () {
System.out.println (tahun + "" + bulan + "" + hari);
}
}
Pilihan Sederhana:
Pilihan Sederhana mirip dengan penyortiran gelembung (Bubble Sort). Setiap kali, nilai paling banyak akan dipilih dari koleksi elemen yang tersisa untuk mengisinya ke posisi saat ini. Satu -satunya perbedaan adalah bahwa penyortiran gelembung menukar lokasi elemen setiap kali ia menemukan bahwa ia lebih kecil (atau lebih besar dari) dari nilai saat ini, sementara penyortiran seleksi sederhana adalah memilih nilai terbanyak dalam elemen yang tersisa dan bertukar data di posisi saat ini.
Misalnya, untuk set elemen r = {37, 40, 38, 42, 461, 5, 7, 9, 12}
Dalam urutan pertama: 37 secara langsung ditukar dengan 5, membentuk urutan baru R1 = {5,40,38,42,461,37,7,9,12}
Dalam urutan kedua: 40 secara langsung ditukar dengan 7, membentuk urutan baru R2 = {5,7,38,42,461,37,40,9,12}
Dan seterusnya sampai elemen terakhir (Catatan: dalam urutan kedua, 38 lebih kecil dari 42, tetapi mereka tidak bertukar data).
Berikut adalah versi implementasi Java yang hanya memilih penyortiran:
Salinan kode adalah sebagai berikut:
public static void selectionsort (int [] data) {
if (data == null || data.length <= 1)
kembali;
int i, j, nilai, minpos, len = data.length;
int luar = len - 1, tmp;
untuk (i = 0; i <luar; i ++) {
nilai = data [i];
minpos = -1;
untuk (j = i+1; j <len; j ++) {
if (data [j] <value) {
minpos = j;
nilai = data [j];
}
}
if (minpos! = -1) {
tmp = data [i];
data [i] = nilai;
data [minpos] = tmp;
}
// untuk (int k = 0; k <len; k ++) {
// System.out.print (data [k] + ",");
//}
// System.out.println ();
}
}
public static void main (string [] args) {
int [] coll = {
37, 40, 38, 42, 461, 5, 7, 9, 12
};
Selectionsort (coll);
untuk (int i = 0; i <coll.length; i ++) {
System.out.print (coll [i] + ",");
}
}
Sortir Pilihan Pohon
Algoritma penyortiran pemilihan pohon adalah algoritma khas yang memperdagangkan ruang untuk waktu dibandingkan dengan penyortiran seleksi sederhana. Idenya adalah untuk memperlakukan elemen N yang diurutkan, membangun angka yang relatif kecil (n+1)/2, dan kemudian membangun angka yang relatif kecil [n+1]/4 sampai hanya ada satu elemen. Dibangun menjadi pohon yang benar -benar biner.
Saat menyortir, elemen adalah yang terkecil.
Berikut adalah versi implementasi Java dari penyortiran pemilihan pohon:
Salinan kode adalah sebagai berikut:
public static void TreeselectionSort (int [] data) {
if (data == null || data.length <= 1)
kembali;
int len = data.length, low = 0, i, j;
// Tambahkan ruang tambahan
int [] tmp = int int [2*len -1];
int tsize = tmp.length;
// Bangun pohon
untuk (i = len-1, j = tmp.length-1; i> = 0; i-, j-) {
tmp [j] = data [i];
}
untuk (i = tsize -1; i> 0; i- = 2) {
tmp [(i-1)/2] = tmp [i]> tmp [i-1]?
}
//akhir
// Lepaskan simpul minimum.
while (rendah <len) {
Data [rendah ++] = TMP [0];
untuk (j = tsize-1; tmp [j]! = tmp [0]; j--);
tmp [j] = integer.max_value;
while (j> 0) {
if (j%2 == 0) {// Jika itu adalah simpul yang tepat
tmp [(j-1)/2] = tmp [j]> tmp [j-1]? tmp [j-1]: tmp [j];
j = (j-1)/2;
} else {// jika itu adalah simpul kiri
tmp [j/2] = tmp [j]> tmp [j+1]?
j = j/2;
}
}
}
}
Saat membangun pohon biner lengkap, ruang tambahan 2*n -1 diperlukan untuk kumpulan elemen N.
Kode:
Salinan kode adalah sebagai berikut:
while (j> 0) {
if (j%2 == 0) {// Jika itu adalah simpul yang tepat
tmp [(j-1)/2] = tmp [j]> tmp [j-1]? tmp [j-1]: tmp [j];
j = (j-1)/2;
} else {// jika itu adalah simpul kiri
tmp [j/2] = tmp [j]> tmp [j+1]?
j = j/2;
}
}
Kemudian terapkan konstruksi rekursif dari nilai minimum di set baru.