Perkenalan
Kompleksitas Mergesort untuk input yang telah diurutkan secara terbalik adalah O (n^2), dan Timsort dihasilkan dengan mengoptimalkan mergeSort untuk situasi ini. Kompleksitas rata -rata adalah n*o (log n), kasus terbaik adalah O (n), dan kasus terburuk adalah n*o (log n). Dan Timsort adalah jenis stabilitas. Idenya adalah untuk mempartisi kolom yang diurutkan terlebih dahulu, dan kemudian menggabungkan partisi, yang terlihat sama dengan langkah mergeSort, tetapi ada beberapa optimisasi untuk data terbalik dan skala besar.
Ide optimasi menggabungkan penyortiran
Ada beberapa metode optimasi untuk menggabungkan penyortiran:
Seperti penyortiran cepat, Anda dapat menggunakan penyortiran insert atau memilih penyortiran untuk array kecil untuk menghindari panggilan rekursif.
Sebelum penggabungan () dipanggil, Anda dapat menentukan apakah [mid] kurang dari atau sama dengan [mid+1]. Jika demikian, maka tidak perlu bergabung, array sudah dipesan. Alasannya sangat sederhana. Karena kedua subarray sudah dipesan, [mid] adalah nilai maksimum dari subarray pertama, dan [mid+1] adalah nilai minimum subarray kedua. Ketika [mid] <= a [mid+1], array dipesan secara keseluruhan.
Untuk menghemat waktu menyalin elemen ke array tambahan, peran array asli dan array tambahan dapat ditukar pada setiap tingkat panggilan rekursif.
Proses penggabungan dalam metode merge () perlu menentukan apakah saya dan j telah melintasi batas, yaitu, setengah dari tepi telah digunakan. Cara lain untuk menghapus kode yang mendeteksi apakah setengah sisi telah habis. Langkah spesifik adalah menyalin paruh kedua dari array A [] ke aux [] dalam urutan menurun, dan kemudian bergabung dari kedua ujungnya. Untuk array {1,2,3} dan {2,3,5}, subarray pertama disalin seperti biasa, dan yang kedua disalin dari belakang ke depan, dan elemen terakhir dalam aux [] adalah {1,2,3,5,3,2}. Kerugian dari metode ini adalah membuat penyortiran gabungan menjadi penyortiran yang tidak stabil. Implementasi kode adalah sebagai berikut:
void gabungan (int [] a, int lo, int mid, int hi, int [] aux) {for (int k = lo; k <= mid; k ++) {aux [k] = a [k];} untuk (int k = mid+1; k <= hi; k ++) {aux [k] = a [hai - k+1]; // dari dua ujung ke tengah untuk (int k = lo; k <= hi; k ++) if (aux [i] <= aux [j]) a [k] = aux [i ++]; lain a [k] = aux [j--];}Langkah Timsort
Partisi
Gagasan partisi adalah untuk memindai array sekali, dan menggunakan urutan positif kontinu (jika diurutkan urutan naik, maka urutan positif adalah urutan naik), atau [ketat] (untuk memastikan stabilitas algoritma penyortiran) sebagai partisi (dijalankan). Jika itu adalah urutan terbalik, balikkan elemen -elemen di partisi. Misalnya
1, 2, 3, 6, 4, 5, 8, 6, 4 Hasil partisi adalah
[1,2,3,6], [4,5,8], [6,4]
Kemudian membalikkan urutan terbalik
[1,2,3,6], [4,5,8], [4,6]
menggabungkan
Pertimbangkan contoh ekstrem, misalnya, panjang partisi adalah 10.000, 10, 1000, 10, 10, dan 10, tentu saja kami berharap dapat menggabungkan 10 10 menjadi 20, 20 dan 1000 menjadi 1020 terlebih dahulu. Jika kita bergabung dari kiri ke kanan, kita akan menggunakan array 10000 dan kombinasi jumlah kecil setiap kali, yang terlalu mahal. Jadi kita dapat menggunakan strategi untuk mengoptimalkan urutan penggabungan.
Contoh
Mengambil comparableTimsort.sort () di Java sebagai contoh, tumpukan run digunakan untuk menentukan apakah itu harus digabungkan.
if (nremaining <min_merge) {int initrunlen = countrunandmakeascending (a, lo, hai); Binarysort (a, lo, hai, lo + initrunlen); kembali; }Urutkan kurang dari min_merge (32), dan urutkan langsung dengan penyisipan biner setelah dipartisi
int minrun = minrunlength (nremaining); lakukan {// Cari tahu posisi awal dari partisi berikutnya, dan juga balikkan urutan terbalik int runlen = countrunandmakeascending (a, lo, hai); // Pastikan run dalam run stack lebih besar dari MinRun. Jika partisi saat ini terlalu kecil, keluarkan elemen -elemen dari belakang untuk menebus jika (runlen <minrun) {int force = nremaining <= minrun? nremaining: MinRun; Binarysort (a, lo, lo + force, lo + runlen); runlen = force; } // Letakkan lari ke run stack ts.pushrun (lo, runlen); // menilai apakah itu harus digabungkan. Saya mulai dari bagian atas tumpukan dan tahu bahwa itu tidak dapat digabungkan // 1. runlen [i - 3]> runlen [i - 2] + runlen [i - 1] // 2. runlen [i - 2]> runlen [i - 1] ts.mergecollapse (); lo += runlen; nremaining -= runlen; } while (nremaining! = 0); // Gabungkan semua lari yang tersisa untuk menyelesaikan Sort Sorts Assert lo == hai; // gabungkan sisa run ts.mergeforcollapse (); menegaskan ts.stacksize == 1;Melihat fungsi yang lebih penting
/*** If the lengths of the last 2 runs are added longer than the previous one, then use the run at the middle position and the run with a shorter front and back lengths to merge* If the lengths of the last 2 runs are added shorter than the previous one, then merge the two runs*/ private void mergeCollapse() { while (stackSize > 1) { int n = stackSize - 2; if (n> 0 && runlen [n-1] <= runlen [n] + runlen [n + 1]) {if (runlen [n-1] <runlen [n + 1]) n--; mergeat (n); } lain jika (runlen [n] <= runlen [n + 1]) {mergeat (n); } else {break; // invarian didirikan}}