Efisiensi penyortiran umumnya dibandingkan dari tiga aspek: jumlah perbandingan data, jumlah perpindahan data, dan jumlah ruang memori yang digunakan.
Mari kita membuat perbandingan umum tentang pengurutan gelembung, pengurutan pilihan, pengurutan penyisipan, dan pengurutan cepat. Algoritma pengurutan gelembung umumnya tidak digunakan karena jumlah perbandingan dan perpindahannya paling banyak di antara beberapa algoritma pengurutan. Satu-satunya kelebihannya adalah algoritmanya sederhana dan mudah dipahami, sehingga dapat digunakan ketika jumlah datanya sedikit akan menjadi beberapa nilai aplikasi. Selection sort mempunyai jumlah perbandingan yang sama dengan bubble sort yaitu n kuadrat, namun mengurangi jumlah pertukaran seminimal mungkin, sehingga dapat diterapkan ketika jumlah data sedikit dan pertukaran data lebih memakan waktu dibandingkan membandingkan. data.Pilih pengurutan.
Dalam kebanyakan kasus, ketika jumlah data relatif kecil atau pada dasarnya terurut, algoritma pengurutan penyisipan adalah pilihan terbaik. Untuk menyortir data dalam jumlah besar, quicksort biasanya merupakan metode terbaik.
Algoritme pengurutan di atas hanya memakan sedikit ruang memori dan hanya memerlukan variabel tambahan untuk menyimpan sementara item data selama pertukaran. Oleh karena itu, tidak ada perbandingan besarnya ruang memori yang digunakan.
Jumlah perbandingan jenis penyisipan masih n kuadrat, namun secara umum dua kali lebih cepat dibandingkan jenis gelembung dan sedikit lebih cepat dibandingkan jenis seleksi. Ini sering digunakan pada tahap akhir algoritma pengurutan yang kompleks, seperti quicksort.
Algoritma: Setelah pemrosesan i-1, L[1..i-1] telah diurutkan. Pass ke-i hanya memasukkan L[i] ke posisi yang sesuai dari L[1..i-1],
Sehingga L[1..i] merupakan barisan terurut lagi. Untuk mencapai tujuan ini, kita dapat menggunakan perbandingan sekuensial.
Pertama bandingkan L[i] dan L[i-1]. Jika L[i-1]<=L[i], maka L[1..i] telah diurutkan dan proses ke-i selesai;
Jika tidak, tukarkan posisi L[i] dan L[i-1], dan terus bandingkan L[i-1] dan L[i-2] hingga posisi j (1≤j≤i-1) tertentu tercapai ditemukan.
Sampai L[j] ≤L[j+1]
Keuntungan: lebih sedikit elemen yang dipindahkan dan hanya diperlukan ruang tambahan
Kompleksitas waktu n*n
Ini adalah metode pengurutan yang baik jika jumlah n record yang akan diurutkan sedikit. Namun bila n sangat besar, hal ini tidak tepat
Contoh: int[] nilai = { 5, 2, 4, 1, 3 };
Proses penyortiran:
Pertama kali: 2,5,4,1,3
Kedua kalinya: 2,4,5,1,3
Ketiga kalinya: 1,2,4,5,3
Kali ke-4: 1,2,3,4,5
kode jawa:
Copy kode kodenya sebagai berikut:
kelas publik InsertSort {
public static void main(String[] args) {
int[] nilai = { 5, 2, 4, 1, 3 };
urutkan(nilai);
for (int i = 0; i < nilai.panjang; ++i) {
Sistem.keluar.println(nilai[i]);
}
}
pengurutan kekosongan statis publik(nilai int[]) {
ke suhu;
ke dalam j = 0;
for (int i = 1; i < nilai.panjang; i++) {
if(values[i]<values[i-1])//Penilaian di sini sangat penting. Hal ini mencerminkan alasan mengapa pengurutan penyisipan lebih cepat daripada pengurutan gelembung dan pengurutan pilihan.
{
suhu = nilai[i];
//Memindahkan data ke belakang
untuk (j=i-1; j>=0 && suhu<nilai[j]; j--)
{
nilai[j+1] =nilai[j];
}
//Masukkan data ke posisi j+1
nilai[j+1] =temp;
Sistem.keluar.cetak("th" + (i + 1) + "th:");
for (int k = 0; k < nilai.panjang; k++) {
Sistem.keluar.cetak(nilai[k]+",");
}
Sistem.keluar.println("");
}
}
}
}
Contoh kedua
Copy kode kodenya sebagai berikut:
paket cn.cqu.coce.xutao;
kelas publik zhijiecharu {
public static void main(String args[]){
int a[]={1,2,34,67,8,9,6,7,56,34,232,99};
ke dalam aku,j,k;
for(i=0;i<a.panjang;i++)
Sistem.keluar.cetak(a[i]+"/t");
Sistem.keluar.println();
for(i=1;i<a.panjang;i++){
untuk(j=i-1;j>=0;j--)
jika(sebuah[i]>sebuah[j])
merusak;
jika(j!=i-1){
ke suhu;
suhu=a[i];
untuk(k=i-1;k>j;k--)
sebuah[k+1]=sebuah[k];
a[k+1]=temp;
}
}
for(i=0;i<a.panjang;i++)
Sistem.keluar.cetak(a[i]+"/t");
Sistem.keluar.println();
}
}