Algoritme pengurutan digunakan di banyak tempat. Saya baru-baru ini meninjau kembali algoritma tersebut dan menerapkannya sendiri. Saya akan mencatatnya di sini dan menyimpan beberapa bahan untuk ditinjau di masa mendatang.
Tanpa basa-basi lagi, mari kita lihat algoritma pengurutan klasik satu per satu:
1. Pilih pengurutan
Ide dasar pengurutan seleksi adalah selama proses melintasi array, jika i mewakili nomor urut saat ini yang perlu diurutkan, Anda perlu mencari nilai minimum di antara [i...n-1] yang tersisa. , lalu arahkan nilai minimum yang ditemukan ke nilai i yang dipertukarkan. Karena setiap proses penentuan elemen akan memiliki subproses pemilihan nilai maksimal, maka orang dengan gamblang menyebutnya pengurutan seleksi. Mari kita ambil contoh:
Awal: [38, 17, 16, 16, 7, 31, 39, 32, 2, 11]
i = 0: [2, 17, 16, 16, 7, 31, 39, 32, 38, 11] (0 [38]<->8 [2])
i = 1: [2, 7, 16, 16, 17, 31, 39, 32, 38, 11] (1 [38]<->4 [17])
i = 2: [2, 7, 11, 16, 17, 31, 39, 32, 38, 16] (ke-2 [11]<->ke-9 [16])
i = 3: [2, 7, 11, 16, 17, 31, 39, 32, 38, 16] (tidak perlu ditukar)
i = 4: [2, 7, 11, 16, 16, 31, 39, 32, 38, 17] (ke-4 [17]<->ke-9 [16])
i = 5: [2, 7, 11, 16, 16, 17, 39, 32, 38, 31] (5 [31]<->9 [17])
i = 6: [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] (6 [39]<->9 [31])
i = 7: [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] (tidak perlu ditukar)
i = 8: [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] (tidak perlu ditukar)
i = 9: [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] (tidak perlu ditukar)
Seperti dapat dilihat dari contoh, seiring berjalannya pengurutan pilihan (i secara bertahap meningkat), jumlah perbandingan akan semakin berkurang. Namun, terlepas dari apakah array diurutkan pada awalnya atau tidak, pengurutan pilihan akan melakukan perbandingan pilihan dari i sampai akhir array. Jadi untuk array dengan panjang tertentu, jumlah perbandingan dalam pengurutan pilihan adalah tetap: 1 + 2 + 3 + … + n = n * (n + 1) / 2 , dan jumlah pertukaran terkait dengan urutan larik awal. Jika urutan larik awal acak, maka dalam kasus terburuk, elemen larik akan ditukar sebanyak n kali, dan dalam kasus terbaik mungkin 0 kali ( array itu sendiri adalah urutan).
Dapat disimpulkan bahwa kompleksitas waktu dan kompleksitas ruang dari pengurutan pilihan adalah O(n2) dan O(1) (pengurutan pilihan hanya memerlukan ruang ekstra untuk pertukaran elemen array).
Kode implementasi:
Copy kode kodenya sebagai berikut:
/**
* Penyortiran Seleksi
*/
PILIHAN(Tabel Sortir baru() {
public <T extends Comparable<T>> void sort(T[] array, boolean ascend) {
int len = array.panjang;
untuk (int saya = 0; saya < len; saya++) {
int dipilih = i;
untuk (int j = i + 1; j < len; j++) {
int bandingkan = array[j].compareTo(array[yang dipilih]);
if (bandingkan != 0 && bandingkan < 0 == naik) {
dipilih = j;
}
}
pertukaran(array, i, dipilih);
}
}
})
2. Sortir penyisipan
Ide dasar dari insertion sort adalah selama proses traversing array, dengan asumsi elemen sebelum nomor urut i yaitu [0..i-1] telah terurut, perjalanan ini perlu mencari posisi yang benar k dari elemen x yang bersesuaian dengan i, dan Dalam proses mencari posisi k ini, elemen-elemen yang dibandingkan dipindahkan kembali satu posisi satu per satu untuk "memberi ruang" bagi elemen x. Terakhir, nilai elemen yang bersesuaian dengan k ditugaskan ke x.Urutan penyisipan juga diberi nama sesuai dengan karakteristik pengurutan.
Berikut ini contohnya: Angka-angka yang diberi tanda merah adalah bilangan-bilangan yang disisipkan, bilangan-bilangan yang dicoret adalah unsur-unsur yang tidak ikut dalam pengurutan ini satu per satu, seperti Elemen yang ikut dalam pengurutan kedua adalah [11, 31, 12], dan elemen yang perlu disisipkan adalah 12, tetapi 12 saat ini belum berada pada posisi yang benar, jadi kita perlu menyisipkannya dengan elemen sebelumnya 31 dan 11 secara berurutan. Bandingkan, pindahkan elemen yang dibandingkan saat membandingkan, dan hentikan perbandingan ketika Anda menemukan elemen pertama 11 yang lebih kecil dari 12. Saat ini, indeks 1 yang bersesuaian dengan 31 adalah posisi di mana 12 perlu disisipkan.
Awal: [11, 31, 12, 5, 34, 30, 26, 38, 36, 18]
Pass pertama: [11, 31, 12, 5, 34, 30, 26, 38, 36, 18] (tidak ada elemen yang dipindahkan)
Perjalanan kedua: [11, 12, 31, 5, 34, 30, 26, 38, 36, 18] (31 gerakan mundur)
Perjalanan ketiga: [5, 11, 12, 31, 34, 30, 26, 38, 36, 18] (11, 12, 31 semuanya mundur)
Pass keempat: [5, 11, 12, 31, 34, 30, 26, 38, 36, 18] (tidak ada elemen bergerak)
Perjalanan kelima: [5, 11, 12, 30, 31, 34, 26, 38, 36, 18] (31, 34 bergerak mundur)
Perjalanan keenam: [5, 11, 12, 26, 30, 31, 34, 38, 36, 18] (30, 31, 34 bergerak mundur)
Pass ketujuh: [5, 11, 12, 26, 30, 31, 34, 38, 36, 18] (tidak ada elemen bergerak)
Perjalanan kedelapan: [5, 11, 12, 26, 30, 31, 34, 36, 38, 18] (38 gerakan mundur)
Perjalanan kesembilan: [5, 11, 12, 18, 26, 30, 31, 34, 36, 38] (26, 30, 31, 34, 36, 38 bergerak mundur)
Pengurutan penyisipan lebih baik daripada pengurutan pilihan karena dapat memanfaatkan fakta bahwa bagian pertama dari elemen array telah diurutkan selama proses pengurutan, sehingga secara efektif mengurangi jumlah perbandingan Pada akhirnya, dalam kasus yang buruk (array yang diberikan berada dalam urutan terbalik) jumlah perbandingan dan pergerakan yang diperlukan untuk pengurutan penyisipan akan sama dengan 1 + 2 + 3... + n = n * (n + 1) / 2. Dalam kasus ekstrim ini, penyisipan semacam Efisiensi penyortiran bahkan lebih buruk daripada penyortiran pilihan. Oleh karena itu, pengurutan penyisipan adalah metode pengurutan yang tidak stabil, dan efisiensi penyisipan berkaitan erat dengan urutan awal larik. Secara umum, kompleksitas waktu dan kompleksitas ruang dari insertion sort masing-masing adalah O(n2) dan O(1).
Kode implementasi:
Copy kode kodenya sebagai berikut:
/**
* Penyortiran Penyisipan
*/
INSERTION(Tabel Sortir baru() {
public <T extends Comparable<T>> void sort(T[] array, boolean ascend) {
int len = array.panjang;
untuk (int saya = 1; saya < len; saya++) {
T keSisipkan = larik[i];
int j = saya;
untuk (; j > 0; j) {
int bandingkan = array[j - 1].compareTo(toInsert);
if (bandingkan == 0 || bandingkan < 0 == naik) {
merusak;
}
susunan[j] = susunan[j - 1];
}
array[j] = keSisipkan;
}
}
})
3. Penyortiran gelembung
Penyortiran gelembung dapat dikatakan sebagai algoritma pengurutan yang paling klasik. Saya ingat algoritma ini adalah algoritma yang pertama kali saya gunakan ketika saya masih di sekolah loop dalam, dinilai apakah dua elemen yang berdekatan berada dalam urutan terbalik. Jika demikian, tukarkan kedua elemen dan lakukan satu loop luar untuk "mengambang" elemen terkecil di antara elemen yang tersisa dalam array ke depan, sehingga disebut demikian disebut penyortiran gelembung.
Mari kita beri contoh sederhana seperti biasa:
Keadaan awal: [24, 19, 26, 39, 36, 7, 31, 29, 38, 23]
Perjalanan pertama lapisan dalam: [24, 19, 26, 39, 36, 7, 31, 29, 23, 38] (9 [23]<->8 [38)
Jalur kedua dari lapisan dalam: [24, 19, 26, 39, 36, 7, 31, 23, 29, 38] (8 [23]<->7 [29])
Jalur ketiga dari lapisan dalam: [24, 19, 26, 39, 36, 7, 23, 31, 29, 38] (7 [23]<->6 [31])
Lintasan keempat dari lapisan dalam: [24, 19, 26, 39, 36, 7, 23, 31, 29, 38] (7 dan 23 semuanya dalam urutan yang benar, tidak perlu pertukaran)
Perjalanan kelima lapisan dalam: [24, 19, 26, 39, 7, 36, 23, 31, 29, 38] (5 [7]<->4 [36])
Perjalanan keenam lapisan dalam: [24, 19, 26, 7, 39, 36, 23, 31, 29, 38] (ke-4 [7]<->ke-3 [39])
Lintasan ketujuh dari lapisan dalam: [24, 19, 7, 26, 39, 36, 23, 31, 29, 38] (ke-3 [7]<->ke-2 [26])
Lintasan kedelapan dari lapisan dalam: [24, 7, 19, 26, 39, 36, 23, 31, 29, 38] (ke-2 [7]<->ke-1 [19])
Perjalanan kesembilan lapisan dalam: [7, 24, 19, 26, 39, 36, 23, 31, 29, 38] (1 [7]<->0 [24])
..........
Sebenarnya bubble sort mirip dengan Selection Sort, jumlah perbandingannya sama yaitu n*(n+1)/2. Namun bubble sort akan melakukan pertukaran tambahan pada proses pemilihan nilai minimalnya (bubble sort hanya perlu melakukan pertukaran saja). Jika ternyata urutan elemen yang berdekatan tidak benar, maka akan ditukar. Sejalan dengan itu, penyortiran pilihan hanya akan memutuskan apakah akan menukar sesuai dengan situasi setelah perbandingan loop dalam selesai), jadi menurut saya, penyortiran pilihan termasuk. untuk penyortiran gelembung.
Kode implementasi:
Copy kode kodenya sebagai berikut:
/**
* Penyortiran Gelembung, mirip sekali dengan Penyortiran Penyisipan
*/
BUBBLE(yang Dapat Diurutkan baru() {
public <T extends Comparable<T>> void sort(T[] array, boolean ascend) {
int panjang = array.panjang;
int lastExchangedIdx = 0;
untuk (int i = 0; i < panjang; i++) {
// tandai tanda pada identitas apakah terjadi pertukaran yang salah
boolean isExchanged = salah;
// perbandingan dan pertukaran terakhir terjadi sebelum mencapai indeks i
int currOrderedIdx = lastExchangedIdx > saya ? lastExchangedIdx : saya;
untuk (int j = panjang 1; j > currOrderedIdx; j) {
int bandingkan = array[j - 1].compareTo(array[j]);
if (bandingkan != 0 && bandingkan > 0 == naik) {
pertukaran(array, j 1, j);
isExchanged = benar;
lastExchangedIdx = j;
}
}
// jika tidak terjadi pertukaran berarti array sudah terurut
jika (dipertukarkan == salah) {
merusak;
}
}
}
})
4. Penyortiran bukit
Penyortiran bukit lahir karena penyortiran penyisipan menghadapi masalah memindahkan terlalu banyak elemen ketika berhadapan dengan array besar. Ide pengurutan Hill adalah untuk "membagi dan menaklukkan" array besar menjadi beberapa array kecil, dibagi berdasarkan celah, seperti array [1, 2, 3, 4, 5, 6, 7, 8]. = 2 untuk dibagi, dapat dibagi menjadi dua larik [1, 3, 5, 7] dan [2, 4, 6, 8] (bersamaan, misalnya gap = 3 , maka array yang terbagi adalah: [1, 4, 7], [2, 5, 8], [3, 6]) Kemudian lakukan pengurutan penyisipan pada array yang terbagi, dan kemudian kurangi setelah setiap sub-array diurutkan. Ulangi langkah sebelumnya hingga gap = 1 , yaitu penyortiran penyisipan dilakukan pada seluruh larik. Pada saat ini, larik pada dasarnya sudah diurutkan, sehingga elemen yang perlu dipindahkan akan sangat kecil, yang memecahkan masalah perpindahan lebih banyak dalam pengurutan penyisipan saat memproses penyortiran besar. array skala.
Silakan merujuk ke pengurutan penyisipan untuk contoh spesifik.
Pengurutan bukit adalah versi penyempurnaan dari pengurutan penyisipan. Ini sangat membantu dalam meningkatkan efisiensi ketika jumlah datanya besar, disarankan untuk menggunakan pengurutan penyisipan secara langsung.
Kode implementasi:
Copy kode kodenya sebagai berikut:
/**
* Penyortiran Kerang
*/
SHELL(yang Dapat Diurutkan baru() {
public <T extends Comparable<T>> void sort(T[] array, boolean ascend) {
int panjang = array.panjang;
int celah = 1;
// gunakan nilai maksimum di sebelah panjang / 3 sebagai celah pertama
while (celah < panjang / 3) {
celah = celah * 3 + 1;
}
sementara (celah >= 1) {
untuk (int i = celah; i < panjang; i++) {
T selanjutnya = larik[i];
int j = saya;
sementara (j >= celah) {
int bandingkan = array[j - gap].bandingkanKe(berikutnya);
// sudah menemukan posisinya
if (bandingkan == 0 || bandingkan < 0 == naik) {
merusak;
}
susunan[j] = susunan[j - celah];
j -= celah;
}
jika (j != saya) {
larik[j] = berikutnya;
}
}
celah /= 3;
}
}
})
5. Gabungkan pengurutan
Pengurutan gabungan diimplementasikan dengan rekursi, yaitu metode "bagi dan taklukkan". Array target dibagi menjadi dua dari tengah, lalu kedua array diurutkan secara terpisah. Setelah pengurutan selesai, kedua array yang diurutkan tersebut "digabungkan " menjadi Together, hal terpenting dalam pengurutan penggabungan adalah proses "penggabungan". Proses penggabungan memerlukan ruang tambahan yang sesuai dengan panjang dua larik yang perlu digabungkan. Misalnya larik yang perlu ditentukan adalah: [3, 6, 8, 11] dan [1, 3, 12, 15] (Meskipun secara logis terbagi menjadi dua larik, elemen-elemen ini sebenarnya masih berada dalam larik asli, namun dibagi menjadi dua larik melalui beberapa indeks. Larik asli Untuk [3, 6, 8, 11, 1, 3, 12, 15, kita menetapkan tiga pointer lo, mid, dan high masing-masing ke 0, 3, dan 7. Pembagian sub-array yang logis dapat dicapai) Maka panjang array tambahan yang dibutuhkan adalah 4 + 4 = 8. Proses penggabungan dapat diringkas secara singkat sebagai berikut:
1) Salin elemen dalam dua sub-array ke array baru copyArray. Mengambil contoh yang disebutkan di atas sebagai contoh, copyArray = [3, 6, 8, 11, 1, 3, 12, 15];
2) Tetapkan dua pointer untuk menunjuk ke elemen pertama yang sesuai dalam array atom. Asumsikan kedua pointer tersebut diberi nama leftIdx dan rightIdx, lalu leftIdx = 0 (sesuai dengan elemen pertama [3] di copyArray), rightIdx = 4 ( sesuai dengan elemen kelima [1] di copyArray);
3) Bandingkan nilai elemen array yang ditunjukkan oleh leftIdx dan rightIdx, pilih yang lebih kecil dan tetapkan nilainya ke posisi i yang sesuai dalam array asli. Setelah penugasan selesai, lakukan operasi kenaikan otomatis pada dua indeks yang berpartisipasi dalam penugasan. Jika nilai leftIdx atau rigthIdx telah mencapai akhir array yang sesuai, yang tersisa hanyalah menyalin elemen array yang tersisa ke posisi yang tersisa secara berurutan.
Berikut adalah contoh spesifik penggabungan:
Perjalanan pertama:
Array bantu [21, 28, 39 |.35, 38] (array dibagi menjadi dua sub-array kiri dan kanan, dipisahkan oleh |)
[21, , , , ] (Pertama kali 21 dibandingkan dengan 35, subarray kiri menang, leftIdx = 0, i = 0)
Perjalanan kedua:
Susunan bantu [21, 28, 39 |.
[21, 28, , , ] (Kedua kalinya 28 dibandingkan dengan 35, subarray kiri menang, leftIdx = 1, i = 1)
Perjalanan ketiga: [21, 28, 39 |.
[21, 28, 35, , ] (Ketiga kalinya 39 dibandingkan dengan 35, subarray kanan menang, rightIdx = 0, i = 2)
Perjalanan keempat: [21, 28, 39 |.
[21, 28, 35, 38,] (Keempat kalinya 39 dan 38 dibandingkan, subarray kanan menang, rightIdx = 1, i = 3)
Perjalanan kelima: [21, 28, 39 |.
[21, 28, 35, 38, 39] (Sub-array kanan telah disalin untuk kelima kalinya, tidak perlu membandingkan leftIdx = 2, i = 4)
Di atas adalah proses penggabungan. Kita dapat membagi seluruh array yang perlu diurutkan beberapa kali (dibagi menjadi dua setiap kali) hingga dibagi menjadi array kecil dengan panjang 1. Jika panjangnya 1, array tidak perlu lagi diurutkan. Setelah itu, array-array ini digabungkan dalam urutan terbalik (karena rekursi) hingga subarray terakhir dengan panjang n/2 digabungkan. Setelah penggabungan selesai, pengurutan array juga selesai.
Pengurutan gabungan memerlukan ruang tambahan paling banyak dari semua pengurutan, dan setiap penggabungan memerlukan jumlah elemen yang sama dengan jumlah panjang dua larik yang berpartisipasi dalam penggabungan (untuk menyediakan larik tambahan). Maka dapat disimpulkan bahwa kompleksitas ruang dari pengurutan gabungan adalah 1 + 2 + 4 + ... + n = n * ( n + 2) / 4 (mengabaikan penilaian paritas n). Di sini, saya juga Lupa berapa ().
Kode implementasi:
Copy kode kodenya sebagai berikut:
/**
* Gabungkan penyortiran
*/
GABUNG(Tabel Sortir baru() {
public <T extends Comparable<T>> void sort(T[] array, boolean ascend) {
this.sort(array, 0, array.length 1, ascend);
}
pribadi <T extends Sebanding<T>> void sort(T[] array, int lo, int hi, boolean ascend) {
// OPTIMALKAN SATU
// jika panjang substring kurang dari 20,
// gunakan penyisipan penyortiran untuk mengurangi pemanggilan rekursif
jika (hai lo < 20) {
untuk (int i = lo + 1; i <= hai; i++) {
T keSisipkan = larik[i];
int j = saya;
untuk (; j > lo; j) {
int bandingkan = array[j - 1].compareTo(toInsert);
if (bandingkan == 0 || bandingkan < 0 == naik) {
merusak;
}
susunan[j] = susunan[j - 1];
}
array[j] = keSisipkan;
}
kembali;
}
int pertengahan = lo + (hai lo) / 2;
sortir(array, lo, mid, ascend);
sort(array, pertengahan +1, hai, naik);
gabung(array, lo, pertengahan, hai, naik);
}
pribadi <T extends Sebanding<T>> void merge(T[] array, int lo, int mid, int hi, boolean ascend) {
// OPTIMALKAN DUA
// jika urutannya sudah benar, lewati penggabungan ini
// karena hal itu tidak perlu dilakukan
int leftEndCompareToRigthStart = array[pertengahan].compareTo(array[pertengahan + 1]);
if (leftEndCompareToRigthStart == 0 || leftEndCompareToRigthStart < 0 == naik) {
kembali;
}
@SuppressWarnings("tidak dicentang")
T[] arrayCopy = (T[]) baru Sebanding[hi - lo + 1];
System.arraycopy(array, lo, arrayCopy, 0, arrayCopy.length);
int Idx rendah = 0;
int highIdx = pertengahan lo + 1;
untuk (int i = lo; i <= hai; i++) {
if (lowIdx > pertengahan lo) {
// sub array kiri habis
array[i] = arrayCopy[highIdx++];
} else if (highIdx > halo) {
// sub array kanan habis
array[i] = arrayCopy[lowIdx++];
} else if (arrayCopy[lowIdx].compareTo(arrayCopy[highIdx]) < 0 == naik) {
array[i] = arrayCopy[lowIdx++];
} kalau tidak {
array[i] = arrayCopy[highIdx++];
}
}
}
})
6. Penyortiran cepat
Penyortiran cepat juga merupakan algoritme pengurutan "bagi dan taklukkan" yang diimplementasikan menggunakan metode penggabungan. Keunggulannya adalah dapat menentukan posisi pengurutan akhir yang benar untuk elemen array di setiap partisi (inti dari algoritme pengurutan) (satu kali). Jika positioningnya akurat, elemen ini tidak akan dipertimbangkan pada siklus berikutnya).