Masukkan sortir secara langsung
1 Ide Penyortiran:
Rekaman yang akan diurutkan dimasukkan ke dalam catatan yang sudah diurutkan R1, R2, ..., R (n-1).
Untuk urutan acak, mulai dari elemen kedua, masukkan elemen ke posisi yang sesuai di elemen sebelum secara bergantian. Elemen sebelum diurutkan.
Pesanan Pertama: Masukkan elemen kedua ke dalam daftar yang dipesan dalam urutan sebelumnya (saat ini hanya ada satu elemen di yang sebelumnya, tentu saja dipesan). Setelah itu, dua elemen pertama dari urutan ini dipesan.
Jenis kedua: Masukkan elemen ketiga ke dalam daftar yang dipesan dari panjang sebelumnya 2 sehingga dua elemen pertama dipesan.
Dan seterusnya sampai elemen ke-n dimasukkan ke dalam daftar yang dipesan dengan panjang sebelumnya (N-1).
2 Implementasi Algoritma:
// Langsung masukkan sort void straight_insert_sort (int num [], int len) {int i, j, key; untuk (j = 1; j <len; j ++) {key = num [j]; i = j-1; while (i> = 0 && num [i]> key) {num [i+1] = num [i]; Saya--; } num [i+1] = key; }}3 Analisis Kinerja:
3.1 Kompleksitas Ruang: Seperti disebutkan di atas, kunci unit tambahan digunakan, dan kompleksitas ruang adalah O (1)
3.2 Kompleksitas Waktu:
3.2.1 Kasus Terbaik: Catatan yang akan diurutkan sudah dipesan, lalu mengurutkannya dalam satu perjalanan, kata kunci dibandingkan sekali, dan catatan dipindahkan dua kali. Seluruh proses
Jumlah perbandingannya
Jumlah catatan yang dipindahkan
Kompleksitas waktu o (n)
3.2.2 Kasus terburuk: Catatan yang akan diurutkan sudah dalam urutan terbalik, maka waktu perbandingan kata kunci adalah I (dari I-1 ke 0), dan catatan bergerak (i+2) kali. Seluruh proses
Jumlah perbandingannya
Jumlah catatan yang dipindahkan
Kompleksitas waktu o (n^2)
3.2.3 Kompleksitas Waktu Rata -rata: O (n^2)
3.3 Stabilitas: Stabil
Lipat setengah insert
1 Ide Penyortiran:
Berdasarkan penyortiran langsung, catatan yang akan diurutkan RI dimasukkan ke dalam catatan yang sudah diurutkan R1, R2, ..., R (n-1). Karena catatan R1, R2, ..., R (N-1) telah diurutkan, "setengah mencari" dapat digunakan saat mencari posisi penyisipan.
2 Implementasi Algoritma:
// lipat setengah insert sort void biner_insert_sort (int num [], int len) {int i, j, key, rendah, tinggi, mid; untuk (i = 1; i <len; i ++) {key = num [i]; rendah = 0; tinggi = I-1; mid = (rendah+tinggi)/2; // Temukan titik penyisipan, titik penyisipan akhir rendah sementara (rendah <= tinggi) {if (tombol <num [mid]) tinggi = mid-1; lain rendah = mid+1; mid = (rendah+tinggi)/2; } // Pindahkan rekaman untuk (j = i; j> low; j-) {num [j] = num [j-1]; } // Masukkan catatan num [rendah] = key; }}3 Analisis Kinerja:
3.1 Kompleksitas Ruang: Seperti disebutkan di atas, kunci unit tambahan digunakan, dan kompleksitas ruang adalah O (1)
3.2 Kompleksitas Waktu: Meskipun pencarian setengah finish mengurangi jumlah catatan dan perbandingan, itu tidak mengurangi jumlah gerakan, sehingga kompleksitas waktu sama dengan algoritma pencarian langsung.
3.2.1 Kasus Terbaik: Kompleksitas Waktu O (N)
3.2.2 Kasus terburuk: Kompleksitas waktu o (n^2)
3.2.3 Kompleksitas Waktu Rata -rata: O (n^2)
3.3 Stabilitas: Stabil