Sepuluh algoritma pengurutan klasik teratas

#Sepuluh algoritma pengurutan klasik (demonstrasi animasi) Dari: blog pribadi Damonare

Teks asli: http://blog.damonare.cn/2016/12/20/十大经典排序算法总结（javascript描述）/

##0. Ikhtisar algoritma

##0.1 Klasifikasi algoritma

Sepuluh algoritma pengurutan umum dapat dibagi menjadi dua kategori besar:

Penyortiran perbandingan waktu nonlinier: Tentukan urutan relatif antar elemen melalui perbandingan. Karena kompleksitas waktunya tidak boleh melebihi O(nlogn), maka disebut pengurutan perbandingan waktu nonlinier. Penyortiran non-perbandingan waktu linier: Ini tidak menentukan urutan relatif antar elemen melalui perbandingan. Ia dapat menembus batas bawah waktu penyortiran berbasis perbandingan dan berjalan dalam waktu linier, sehingga disebut penyortiran non-perbandingan waktu linier.

0.2 Kompleksitas algoritma

0.3 Konsep terkait

Stabil: Jika a awalnya berada di depan b, dan a=b, a akan tetap berada di depan b setelah diurutkan. Tidak stabil: Jika a awalnya berada di depan b, dan a=b, a mungkin muncul setelah b setelah pengurutan. Kompleksitas waktu: jumlah total operasi pada data yang diurutkan. Mencerminkan pola jumlah operasi ketika n berubah. Kompleksitas ruang: mengacu pada pengukuran ruang penyimpanan yang diperlukan ketika suatu algoritma dijalankan di komputer. Ini juga merupakan fungsi dari ukuran data n.

1. Penyortiran Gelembung (Penyortiran Gelembung)

Bubble sort adalah algoritma pengurutan sederhana. Ini berulang kali menelusuri urutan yang akan diurutkan, membandingkan dua elemen sekaligus dan menukarnya jika urutannya salah. Pekerjaan mengunjungi array diulangi sampai tidak diperlukan pertukaran lagi, yang berarti array telah diurutkan. Nama algoritma ini berasal dari fakta bahwa elemen yang lebih kecil akan perlahan-lahan “mengambang” ke bagian atas array melalui pertukaran.

1.1 Deskripsi algoritma

1. Bandingkan elemen yang berdekatan. Jika nilai pertama lebih besar dari nilai kedua, tukar keduanya;

2. Lakukan pekerjaan yang sama untuk setiap pasangan elemen yang berdekatan, dari pasangan pertama di awal hingga pasangan terakhir di akhir, sehingga elemen terakhir adalah bilangan terbesar;

3. Ulangi langkah di atas untuk semua elemen kecuali yang terakhir;

4. Ulangi langkah 1~3 hingga penyortiran selesai.

1.2 Demonstrasi Animasi

1.3 Implementasi kode

function bubbleSort(arr) {
var len = arr.length;
for (var i = 0; i < len - 1; i++) {
for (var j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j+1]) { // 相邻元素两两对比
var temp = arr[j+1]; // 元素交换
arr[j+1] = arr[j];
arr[j] = temp;
}
}
}
return arr;

2. Sortir Seleksi

Seleksi-sortir adalah algoritma pengurutan yang sederhana dan intuitif. Cara kerjanya: Pertama cari elemen terkecil (besar) pada barisan yang belum diurutkan, simpan di awal barisan yang sudah diurutkan, lalu lanjutkan mencari elemen terkecil (besar) dari sisa elemen yang belum diurutkan, lalu letakkan di akhir barisan yang sudah diurutkan. Begitu seterusnya hingga semua elemen terurut.

2.1 Deskripsi algoritma

Penyortiran seleksi langsung dari n record dapat memperoleh hasil yang diurutkan melalui n-1 proses penyortiran seleksi langsung. Algoritma spesifiknya dijelaskan sebagai berikut:

• Keadaan awal: Area tak terurut adalah R[1…n], dan area terurut kosong;
• Ketika pengurutan ke-i (i=1,2,3…n-1) dimulai, luas terurut saat ini dan luas tak terurut masing-masing adalah R[1…i-1] dan R(i…n). Operasi pengurutan ini memilih record R[k] dengan kata kunci terkecil dari area tak berurutan saat ini, dan menukarnya dengan rekaman pertama R di area tak berurutan, sehingga R[1…i] dan R[i+1…n) menjadi area terurut baru dengan jumlah rekaman bertambah 1 dan area tak berurutan baru dengan jumlah rekaman masing-masing berkurang 1;
• Di akhir n-1 lintasan, array diurutkan.

2.2 Demonstrasi Animasi

2.3 Penerapan kode

function selectionSort(arr) {
var len = arr.length;
var minIndex, temp;
for (var i = 0; i < len - 1; i++) {
minIndex = i;
for (var j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) { // 寻找最小的数
minIndex = j; // 将最小数的索引保存
}
}
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
return arr;
}

2.4 Analisis algoritma

Salah satu algoritma pengurutan yang paling stabil, karena data apa pun yang dimasukkan, kompleksitas waktunya adalah O(n2), jadi saat menggunakannya, semakin kecil ukuran datanya, semakin baik. Satu-satunya keuntungannya adalah tidak memakan ruang memori tambahan. Secara teoritis, pengurutan pilihan mungkin juga merupakan metode pengurutan paling umum yang dipikirkan kebanyakan orang saat menyortir.

3. Sortir Penyisipan

Deskripsi algoritma penyisipan-sortir (Insertion-Sort) adalah algoritma pengurutan yang sederhana dan intuitif. Ia bekerja dengan membangun urutan yang teratur. Untuk data yang tidak disortir, ia memindai dari belakang ke depan dalam urutan yang diurutkan, menemukan posisi yang sesuai dan menyisipkannya.

3.1 Deskripsi algoritma

Secara umum, pengurutan penyisipan diimplementasikan pada array menggunakan in-place. Algoritma spesifiknya dijelaskan sebagai berikut:

1. Dimulai dari unsur pertama, unsur tersebut dianggap telah terurut;
2. Keluarkan elemen berikutnya dan pindai dari belakang ke depan dalam urutan elemen yang diurutkan;
3. Jika elemen (yang diurutkan) lebih besar dari elemen baru, pindahkan elemen tersebut ke posisi berikutnya;
4. Ulangi langkah 3 hingga Anda menemukan posisi elemen yang diurutkan lebih kecil atau sama dengan elemen baru;
5. Setelah memasukkan elemen baru ke posisi ini;
6. Ulangi langkah 2~5.

3.2 Demonstrasi GIF

3.3 Penerapan kode

function insertionSort(arr) {
var len = arr.length;
var preIndex, current;
for (var i = 1; i < len; i++) {
preIndex = i - 1;
current = arr[i];
while (preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex + 1] = arr[preIndex];
preIndex--;
}
arr[preIndex + 1] = current;
}
return arr;
}

3.4 Analisis algoritma

Dalam implementasi insertion sort biasanya digunakan in-place sorting (yaitu pengurutan yang hanya menggunakan O(1) spasi ekstra). Oleh karena itu, selama proses pemindaian dari belakang ke depan, elemen yang diurutkan perlu digeser berulang kali dan bertahap ke belakang untuk memberikan ruang penyisipan elemen terbaru.

4. Sortir Kerang

Diciptakan oleh Shell pada tahun 1959, ini adalah algoritma pengurutan pertama yang menerobos O(n2) dan merupakan versi perbaikan dari pengurutan penyisipan sederhana. Ini berbeda dengan jenis penyisipan karena ia membandingkan elemen yang letaknya lebih jauh terlebih dahulu. Pengurutan bukit disebut juga pengurutan pertambahan pereduksi.

4.1 Deskripsi algoritma

Pertama, seluruh urutan record yang akan diurutkan dibagi menjadi beberapa urutan untuk penyortiran penyisipan langsung. Algoritma spesifik dijelaskan:

Pilih barisan tambahan t1, t2,…,tk, dimana ti>tj, tk=1;

Urutkan barisan sebanyak k kali berdasarkan jumlah barisan tambahan k;

Dalam setiap tahap penyortiran, kolom yang akan diurutkan dibagi menjadi beberapa barisan dengan panjang m sesuai dengan pertambahan ti yang sesuai, dan penyortiran penyisipan langsung dilakukan pada setiap subtabel. Hanya jika faktor kenaikannya adalah 1, seluruh barisan diproses sebagai tabel, dan panjang tabel adalah panjang keseluruhan barisan.

4.2 Demonstrasi GIF

4.3 Penerapan kode

function shellSort(arr) {
var len = arr.length,
temp,
gap = 1;
while (gap < len / 3) { // 动态定义间隔序列
gap = gap * 3 + 1;
}
for (gap; gap > 0; gap = Math.floor(gap / 3)) {
for (var i = gap; i < len; i++) {
temp = arr[i];
for (var j = i-gap; j > 0 && arr[j]> temp; j-=gap) {
arr[j + gap] = arr[j];
}
arr[j + gap] = temp;
}
}
return arr;
}

4.4 Analisis algoritma

Inti dari penyortiran bukit terletak pada pengaturan urutan interval. Urutan interval dapat diatur terlebih dahulu atau ditentukan secara dinamis. Algoritma untuk mendefinisikan barisan interval secara dinamis diusulkan oleh Robert Sedgewick, salah satu penulis “Algorithms (Edisi ke-4)”.

5. Gabungkan Sortir

Pengurutan gabungan adalah algoritme pengurutan yang efektif berdasarkan operasi penggabungan. Algoritma ini merupakan aplikasi yang sangat khas yang menggunakan metode membagi dan menaklukkan (Divide and Conquer). Gabungkan urutan yang sudah diurutkan untuk mendapatkan urutan yang terurut sepenuhnya; yaitu, pertama-tama buatlah setiap urutan berikutnya secara teratur, lalu buatlah segmen-segmen berikutnya secara teratur. Jika dua daftar terurut digabungkan menjadi satu daftar terurut, ini disebut penggabungan 2 arah.

5.1 Deskripsi algoritma

Bagilah barisan masukan dengan panjang n menjadi dua barisan dengan panjang n/2;

Gunakan penyortiran gabungan pada dua urutan ini;

Gabungkan dua urutan yang diurutkan menjadi urutan terakhir yang diurutkan.

5.2 Demonstrasi GIF

5.3 Penerapan kode

function mergeSort(arr) { // 采用自上而下的递归方法
var len = arr.length;
if (len < 2) {
return arr;
}
var middle = Math.floor(len / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
var result = [];
while (left.length>0 && right.length>0) {
if (left[0] <= right[0])="" {<="" span="">
result.push(left.shift());
} else {
result.push(right.shift());
}
}
while (left.length)
result.push(left.shift());
while (right.length)
result.push(right.shift());
return result;
}

5.4 Analisis algoritma

Pengurutan gabungan adalah metode pengurutan yang stabil. Seperti halnya pengurutan pilihan, kinerja pengurutan gabungan tidak dipengaruhi oleh data masukan, tetapi kinerjanya jauh lebih baik daripada pengurutan pilihan karena kompleksitas waktunya selalu O(nlogn). Harganya adalah ruang memori tambahan.

6. Penyortiran Cepat

Ide dasar dari penyortiran cepat adalah untuk memisahkan catatan-catatan yang akan diurutkan menjadi dua bagian independen melalui satu penyortiran. Jika kata kunci dari satu bagian catatan lebih kecil dari kata kunci bagian lainnya, maka kedua bagian catatan tersebut dapat diurutkan secara terpisah untuk mencapai urutan seluruh urutan.

6.1 Deskripsi algoritma

Pengurutan cepat menggunakan metode bagi-dan-taklukkan untuk membagi daftar menjadi dua sub-daftar. Algoritma spesifiknya dijelaskan sebagai berikut:

Memilih elemen dari urutan disebut “pivot”;

Susun ulang larik sehingga semua elemen yang lebih kecil dari nilai dasar ditempatkan di depan nilai dasar, dan semua elemen yang lebih besar dari nilai dasar ditempatkan di belakang nilai dasar (angka yang sama dapat ditempatkan di kedua sisi). Setelah partisi ini keluar, basis berada di tengah-tengah urutan. Ini disebut operasi partisi;

Urutkan secara rekursif subarray elemen yang lebih kecil dari nilai dasar dan subarray elemen yang lebih besar dari nilai dasar.

6.2 Demonstrasi GIF

6.3 Penerapan kode

function quickSort(arr, left, right) {
var len = arr.length,
partitionIndex,
left = typeof left != 'number' ? 0 : left,
right = typeof right != 'number' ? len - 1 : right;
if (left < right) {
partitionIndex = partition(arr, left, right);
quickSort(arr, left, partitionIndex-1);
quickSort(arr, partitionIndex+1, right);
}
return arr;
}
function partition(arr, left ,right) { // 分区操作
var pivot = left, // 设定基准值（pivot）
index = pivot + 1;
for (var i = index; i <= right;="" i++)="" {<="" span="">
if (arr[i] < arr[pivot]) {
swap(arr, i, index);
index++;
}
}
swap(arr, pivot, index - 1);
return index-1;
}
function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

7. Sortir Tumpukan

Heapsort mengacu pada algoritma pengurutan yang dirancang menggunakan struktur data heap. Penumpukan adalah struktur yang mendekati pohon biner lengkap dan memenuhi properti penumpukan: yaitu, nilai kunci atau indeks dari simpul anak selalu lebih kecil (atau lebih besar) daripada simpul induknya.

7.1 Deskripsi algoritma

Buatlah urutan awal kata kunci yang akan diurutkan (R1, R2…Rn) menjadi tumpukan atas yang besar, yang merupakan area awal yang tidak berurutan;

Tukarkan elemen teratas R[1] dengan elemen terakhir R[n], lalu dapatkan area tak terurut baru (R1, R2,…Rn-1) dan area terurut baru (Rn), dan penuhi R[1,2…n-1]<=r[n];< span=“”></=r[n];<>

Karena R[1] teratas baru dari heap setelah pertukaran mungkin melanggar properti heap, maka perlu untuk menyesuaikan kembali area tidak teratur saat ini (R1, R2,…Rn-1) menjadi tumpukan baru, dan kemudian menukar R[1] dengan elemen terakhir dari area tidak teratur lagi untuk mendapatkan area tidak teratur baru (R1, R2…Rn-2) dan area terurut baru (Rn-1, Rn). Proses ini diulangi hingga jumlah elemen pada area terurut adalah n-1, maka seluruh proses penyortiran selesai.

7.2 Demonstrasi GIF

7.3 Penerapan kode

var len; // 因为声明的多个函数都需要数据长度，所以把len设置成为全局变量

function buildMaxHeap(arr) { // 建立大顶堆

len = arr.length;

for (var i = Math.floor(len/2); i >= 0; i--) {

heapify(arr, i);

}

}

function heapify(arr, i) { // 堆调整

var left = 2 * i + 1,

right = 2 * i + 2,

largest = i;

if (left < len && arr[left] > arr[largest]) {

largest = left;

}

if (right < len && arr[right] > arr[largest]) {

largest = right;

}

if (largest != i) {

swap(arr, i, largest);

heapify(arr, largest);

}

}

function swap(arr, i, j) {

var temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

}

function heapSort(arr) {

buildMaxHeap(arr);

for (var i = arr.length - 1; i > 0; i--) {

swap(arr, 0, i);

len--;

heapify(arr, 0);

}

return arr;

}

8. Menghitung Sortir

Pengurutan penghitungan bukanlah algoritma pengurutan berdasarkan perbandingan. Intinya terletak pada mengubah nilai data masukan menjadi kunci dan menyimpannya dalam ruang array tambahan yang terbuka. Sebagai pengurutan kompleksitas waktu linier, pengurutan penghitungan mengharuskan data masukan harus berupa bilangan bulat dalam rentang tertentu.

8.1 Deskripsi algoritma

Temukan elemen terbesar dan terkecil dalam array yang akan diurutkan;

Hitung jumlah kemunculan setiap elemen dengan nilai i dalam larik dan simpan di item ke-i larik C;

Akumulasi semua penghitungan (mulai dari elemen pertama di C, setiap item ditambahkan ke item sebelumnya);

Isi array target secara terbalik: Tempatkan setiap elemen i di item ke-C(i) dari array baru, dan kurangi 1 dari C(i) untuk setiap elemen yang ditempatkan.

8.2 Demonstrasi GIF

8.3 Penerapan kode

function countingSort(arr, maxValue) {
var bucket = new Array(maxValue + 1),
sortedIndex = 0;
arrLen = arr.length,
bucketLen = maxValue + 1;
for (var i = 0; i < arrLen; i++) {
if (!bucket[arr[i]]) {
bucket[arr[i]] = 0;
}
bucket[arr[i]]++;
}
for (var j = 0; j < bucketLen; j++) {
while(bucket[j] > 0) {
arr[sortedIndex++] = j;
bucket[j]--;
}
}
return arr;
}

8.4 Analisis Algoritma

Pengurutan penghitungan adalah algoritma pengurutan yang stabil. Jika elemen masukannya adalah n bilangan bulat antara 0 dan k, kompleksitas waktu adalah O(n+k) dan kompleksitas ruang juga O(n+k). Kecepatan penyortirannya lebih cepat daripada algoritma pengurutan perbandingan mana pun. Pengurutan penghitungan adalah algoritma pengurutan yang sangat efektif ketika k tidak terlalu besar dan urutannya relatif terkonsentrasi.

9. Penyortiran Ember

Pengurutan keranjang adalah versi pengurutan penghitungan yang ditingkatkan. Itu memanfaatkan hubungan pemetaan fungsi. Kunci efisiensi terletak pada penentuan fungsi pemetaan ini. Prinsip kerja Bucket sort: Asumsikan data masukan mengikuti distribusi seragam, bagi data ke dalam sejumlah bucket terbatas, lalu urutkan setiap bucket secara terpisah (dimungkinkan untuk menggunakan algoritma pengurutan lain atau terus menggunakan pengurutan bucket secara rekursif).

9.1 Deskripsi algoritma

Tetapkan array kuantitatif sebagai keranjang kosong;

Telusuri data masukan dan masukkan data ke dalam wadah yang sesuai satu per satu;

Sortir setiap ember yang tidak kosong;

Gabungkan data yang diurutkan dari keranjang yang tidak kosong.9.2 Demonstrasi gambar

9.3 Penerapan kode

function bucketSort(arr, bucketSize) {
if (arr.length === 0) {
return arr;
}
var i;
var minValue = arr[0];
var maxValue = arr[0];
for (i = 1; i < arr.length; i++) {
if (arr[i] < minValue) {
minValue = arr[i]; // 输入数据的最小值
} else if (arr[i] > maxValue) {
maxValue = arr[i]; // 输入数据的最大值
}
}
// 桶的初始化
var DEFAULT_BUCKET_SIZE = 5; // 设置桶的默认数量为5
bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
var buckets = new Array(bucketCount);
for (i = 0; i < buckets.length; i++) {
buckets[i] = [];
}
// 利用映射函数将数据分配到各个桶中
for (i = 0; i < arr.length; i++) {
buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
}
arr.length = 0;
for (i = 0; i < buckets.length; i++) {
insertionSort(buckets[i]); // 对每个桶进行排序，这里使用了插入排序
for (var j = 0; j < buckets[i].length; j++) {
arr.push(buckets[i][j]);
}
}
return arr;
}

9.4 Analisis algoritma

Penyortiran keranjang menggunakan waktu linier O(n) dalam kasus terbaik. Kompleksitas waktu pengurutan bucket bergantung pada kompleksitas waktu pengurutan data antar bucket, karena kompleksitas waktu bagian lain adalah O(n). Jelasnya, semakin kecil keranjang yang dibagi, semakin sedikit data yang ada di antara setiap keranjang, dan semakin sedikit waktu yang diperlukan untuk menyortirnya. Namun konsumsi ruang akan meningkat.

10. Sortir Radix

Penyortiran radix adalah mengurutkan berdasarkan urutan rendah terlebih dahulu, lalu mengumpulkan; lalu urutkan berdasarkan urutan tinggi, lalu kumpulkan; dan seterusnya, hingga urutan tertinggi. Terkadang beberapa atribut memiliki urutan prioritas, diurutkan berdasarkan prioritas rendah terlebih dahulu, baru kemudian berdasarkan prioritas tinggi. Urutan terakhirnya adalah yang memiliki prioritas lebih tinggi didahulukan, dan yang memiliki prioritas tinggi dan prioritas lebih rendah sama-sama didahulukan.

10.1 Deskripsi algoritma

Dapatkan jumlah maksimum dalam array dan dapatkan jumlah digitnya;

arr adalah array asli, dan setiap bit diambil dari bit terendah untuk membentuk array radix;

Melakukan pengurutan penghitungan pada radix (menggunakan fitur pengurutan penghitungan yang cocok untuk bilangan rentang kecil);

10.2 Demonstrasi GIF

10.3 Penerapan kode

// LSD Radix Sort
var counter = [];
function radixSort(arr, maxDigit) {
var mod = 10;
var dev = 1;
for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
for(var j = 0; j < arr.length; j++) {
var bucket = parseInt((arr[j] % mod) / dev);
if(counter[bucket]==null) {
counter[bucket] = [];
}
counter[bucket].push(arr[j]);
}
var pos = 0;
for(var j = 0; j < counter.length; j++) {
var value = null;
if(counter[j]!=null) {
while ((value = counter[j].shift()) != null) {
arr[pos++] = value;
}
}
}
}
return arr;
}

10.4 Analisis Algoritma

Penyortiran radix didasarkan pada penyortiran terpisah dan pengumpulan terpisah, sehingga stabil. Namun, kinerja penyortiran radix sedikit lebih buruk daripada penyortiran ember. Setiap alokasi kata kunci dalam kelompok memerlukan kompleksitas waktu O(n), dan memperoleh urutan kata kunci baru setelah alokasi memerlukan kompleksitas waktu O(n). Jika data yang akan diurutkan dapat dibagi menjadi d kata kunci, maka kompleksitas waktu pengurutan radix adalah O(d*2n). Tentu saja, d jauh lebih kecil dari n, sehingga pada dasarnya linear.

Kompleksitas ruang pengurutan radix adalah O(n+k), dengan k adalah jumlah keranjang. Umumnya n >> k, jadi kebutuhan ruang tambahan sekitar n.