Wawancara tertulis sering melibatkan berbagai algoritma. Artikel ini secara singkat memperkenalkan beberapa algoritma yang umum digunakan dan mengimplementasikannya dalam JavaScript.
1. Masukkan penyortiran
1) Pengantar algoritma
Deskripsi algoritma dari penyisipan-sort adalah algoritma penyortiran yang sederhana dan intuitif. Ini bekerja dengan membangun urutan yang dipesan, untuk data yang tidak disortir, memindai ke belakang dan ke depan dalam urutan yang diurutkan, temukan posisi yang sesuai dan masukkan. Dalam implementasi penyortiran penyisipan, penyortiran di tempat biasanya digunakan (yaitu, ruang ekstra O (1) diperlukan), jadi selama proses pemindaian dari belakang ke depan, elemen yang diurutkan perlu berulang kali dipindahkan ke belakang untuk menyediakan ruang penyisipan untuk elemen terbaru.
2) Deskripsi dan implementasi algoritma
Secara umum, penyisipan penyisipan diimplementasikan pada array menggunakan di tempat. Algoritma spesifik digambarkan sebagai berikut:
Mulai dari elemen pertama, elemen dapat dianggap telah diurutkan;
Keluarkan elemen berikutnya dan pindai ke belakang dan ke depan dalam urutan elemen yang sudah diurutkan;
Jika elemen (diurutkan) lebih besar dari elemen baru, pindahkan elemen ke posisi berikutnya;
Ulangi langkah 3 sampai elemen yang diurutkan ditemukan di mana elemen baru kurang dari atau sama;
Setelah memasukkan elemen baru ke posisi itu;
Ulangi langkah 2 hingga 5.
Implementasi Kode JavaScript:
function insertionsort (array) {if (object.prototype.toString.call (array) .slice (8, -1) === 'array') {for (var i = 1; i <array.length; i ++) {var key = array [i]; var j = i - 1; while (j> = 0 && array [j]> key) {array [j + 1] = array [j]; J--; } array [j + 1] = key; } return array; } else {return 'array bukan array!'; }}3) Analisis Algoritma
Kasus Terbaik: Array input diurutkan dalam urutan naik. T (n) = o (n)
Kasus terburuk: Array input diurutkan dalam urutan menurun. T (n) = o (n2)
Rata -rata: t (n) = o (n2)
Dua, jenis penyisipan biner
1) Pengantar algoritma
Penyortiran Biner-Insert-Sort adalah algoritma penyortiran yang membuat perubahan kecil pada algoritma penyortiran penyisipan langsung. Perbedaan terbesar antara itu dan algoritma penyortiran penyisipan langsung adalah bahwa ketika mencari posisi penyisipan, metode pencarian biner digunakan, yang memiliki peningkatan kecepatan tertentu.
2) Deskripsi dan implementasi algoritma
Secara umum, penyisipan penyisipan diimplementasikan pada array menggunakan di tempat. Algoritma spesifik digambarkan sebagai berikut:
Mulai dari elemen pertama, elemen dapat dianggap telah diurutkan;
Keluarkan elemen berikutnya dan temukan posisi angka pertama lebih besar dari itu dalam urutan elemen yang sudah diurutkan;
Setelah memasukkan elemen baru ke posisi itu;
Ulangi dua langkah di atas.
Implementasi Kode JavaScript:
Fungsi BinaryInsionsORT (array) {if (object.prototype.toString.call (array) .slice (8, -1) === 'array') {for (var i = 1; i <array.length; i ++) {var Key = array [i], kiri = 0, kanan = i - panjang; while (kiri <= kanan) {var middle = parseInt ((kiri + kanan) / 2); if (kunci <array [tengah]) {kanan = tengah - 1; } else {left = middle + 1; }} untuk (var j = i-1; j> = left; j--) {array [j + 1] = array [j]; } array [kiri] = key; } return array; } else {return 'array bukan array!'; }}3) Analisis Algoritma
Kasus Terbaik: t (n) = O (nlogn)
Kasus terburuk: t (n) = o (n2)
Rata -rata: t (n) = o (n2)
3. Pilih penyortiran
1) Pengantar algoritma
Seleksi-Sort adalah algoritma penyortiran yang sederhana dan intuitif. Cara kerjanya: Pertama temukan elemen terkecil (besar) dalam urutan yang tidak disortir, simpan di posisi awal dari urutan yang diurutkan, kemudian terus cari elemen terkecil (besar) dari elemen yang tidak disortir yang tersisa, dan kemudian letakkan di ujung urutan yang diurutkan. Dan seterusnya sampai semua elemen diurutkan.
2) Deskripsi dan implementasi algoritma
Pemilihan langsung catatan N dapat diperoleh melalui N-1 Pass untuk secara langsung memilih dan mengurutkan. Algoritma spesifik digambarkan sebagai berikut:
Keadaan awal: area yang tidak tertib adalah R [1..n], dan area yang dipesan kosong;
Ketika pemesanan i-th (i = 1,2,3 ... n-1) dimulai, area yang dipesan dan tidak tertib saat ini adalah R [1..i-1] dan r (i..n) masing-masing. Perintah ini memilih catatan R [k] dengan kata kunci terkecil dari area yang tidak tertib saat ini, dan menukarnya dengan catatan pertama dari area yang tidak tertib, sehingga r [1..i] dan r [i+1..n) menjadi area yang dipesan baru dengan satu peningkatan jumlah catatan dan area baru yang tidak tertib dengan satu penurunan jumlah catatan;
Perjalanan N-1 berakhir dan array dipesan.
Implementasi Kode JavaScript:
function selectionsort (array) {if (object.prototype.toString.call (array) .slice (8, -1) === 'array') {var len = array.length, temp; untuk (var i = 0; i <len - 1; i ++) {var min = array [i]; untuk (var j = i+1; j <len; j ++) {if (array [j] <min) {temp = min; min = array [j]; array [j] = temp; }} array [i] = min; } return array; } else {return 'array bukan array!'; }}3) Analisis Algoritma
Kasus Terbaik: T (n) = O (N2)
Kasus terburuk: t (n) = o (n2)
Rata -rata: t (n) = o (n2)
4. Penyortiran gelembung
1) Pengantar algoritma
Penyortiran gelembung adalah algoritma penyortiran sederhana. Ini berulang kali mengunjungi urutan yang akan diurutkan, membandingkan dua elemen sekaligus, dan menukarnya jika mereka salah. Pekerjaan mengunjungi urutan diulang sampai tidak ada pertukaran yang diperlukan, yaitu urutan telah diurutkan. Asal usul algoritma ini adalah karena semakin kecil elemen akan perlahan -lahan "melayang" ke bagian atas urutan melalui Exchange.
2) Deskripsi dan implementasi algoritma
Algoritma spesifik digambarkan sebagai berikut:
Bandingkan elemen yang berdekatan. Jika yang pertama lebih besar dari yang kedua, bertukar dua dari mereka;
Lakukan pekerjaan yang sama untuk setiap pasangan elemen yang berdekatan, dari awal pasangan pertama hingga akhir pasangan terakhir, sehingga elemen terakhir harus menjadi angka terbesar;
Ulangi langkah -langkah di atas untuk semua elemen kecuali yang terakhir;
Ulangi langkah 1 hingga 3 sampai penyortiran selesai.
Implementasi Kode JavaScript:
function bubblesort (array) {if (object.prototype.toString.call (array) .slice (8, -1) === 'array') {var len = array.length, temp; untuk (var i = 0; i <len - 1; i ++) {for (var j = len - 1; j> = i; j--) {if (array [j] <array [j - 1]) {temp = array [j]; array [j] = array [j - 1]; array [j - 1] = temp; }}} return array; } else {return 'array bukan array!'; }}3) Analisis Algoritma
Kasus Terbaik: t (n) = o (n)
Kasus terburuk: t (n) = o (n2)
Rata -rata: t (n) = o (n2)
5. Sortir Cepat
1) Pengantar algoritma
Ide dasar penyortiran cepat: Bagilah catatan yang akan diurutkan menjadi dua bagian independen melalui satu pesanan, dan kata kunci dari beberapa catatan lebih kecil daripada bagian lain. Maka kedua catatan tersebut dapat terus mengurutkannya secara terpisah untuk mencapai urutan seluruh urutan.
2) Deskripsi dan implementasi algoritma
Penyortiran cepat menggunakan metode pemisah untuk membagi string menjadi dua sub-daftar. Algoritma spesifik digambarkan sebagai berikut:
Memilih elemen dari urutan disebut "prinsip" (pivot);
Pesan ulang urutannya, semua elemen dengan nilai referensi lebih kecil dari ditempatkan di depan referensi, dan semua elemen dengan lebih besar dari nilai referensi ditempatkan di belakang referensi (angka yang sama dapat ditempatkan di kedua sisi). Setelah partisi ini keluar, referensi berada di tengah urutan. Ini disebut operasi partisi;
Urutkan secara rekursif sub-urutan lebih kecil dari elemen referensi dan sub-sekuens lebih besar dari elemen referensi.
Implementasi Kode JavaScript:
//Method one function quickSort(array, left, right) { if (Object.prototype.toString.call(array).slice(8, -1) === 'Array' && typeof left === 'number' && typeof right === 'number') { if (left < right) { var x = array[right], i = left - 1, temp; untuk (var j = kiri; j <= kanan; j ++) {if (array [j] <= x) {i ++; temp = array [i]; array [i] = array [j]; array [j] = temp; }} quicksort (array, kiri, i - 1); quicksort (array, i + 1, kanan); }; } else {return 'array bukan array atau kiri atau kanan bukan nomor!'; }} var aaa = [3, 5, 2, 9, 1]; quicksort (aaa, 0, aaa.length - 1); Console.log (AAA); // metode 2 var quicksort = fungsi (arr) {if (arr.length <= 1) {return arr; } var pivotIndex = math.floor (arr.length / 2); var pivot = arr.splice (pivotIndex, 1) [0]; var left = []; var right = []; untuk (var i = 0; i <arr.length; i ++) {if (arr [i] <pivot) {left.push (arr [i]); } else {right.push (arr [i]); }} return quicksort (kiri) .concat ([pivot], quicksort (kanan)); };3) Analisis Algoritma
Kasus Terbaik: t (n) = O (nlogn)
Kasus terburuk: t (n) = o (n2)
Rata -rata: t (n) = o (nlogn)
6. Heap Sorting
1) Pengantar algoritma
Penyortiran Heap mengacu pada algoritma penyortiran yang dirancang menggunakan struktur data heap. Penumpukan adalah struktur yang kira -kira benar -benar pohon biner dan memenuhi sifat penumpukan: yaitu, nilai kunci atau indeks simpul anak selalu lebih kecil dari (atau lebih besar dari) simpul induknya.
2) Deskripsi dan implementasi algoritma
Algoritma spesifik digambarkan sebagai berikut:
Urutan awal kata kunci yang akan diurutkan (R1, R2 ... RN) dibangun menjadi tumpukan atas yang besar, yang merupakan area awal yang tidak tertib;
Pertukaran elemen teratas heap r [1] dengan elemen terakhir r [n], dan pada saat ini, wilayah baru yang tidak berurutan (R1, R2, ... RN-1) dan wilayah yang dipesan baru (RN) diperoleh, dan R [1,2 ... N-1] <= R [N] puas;
Karena heap teratas baru R [1] setelah pertukaran dapat melanggar sifat-sifat tumpukan, perlu untuk menyesuaikan area yang tidak tertib saat ini (R1, R2, ... RN-1) ke tumpukan baru, dan kemudian bertukar R [1] dengan elemen terakhir dari area yang tidak tertib lagi untuk mendapatkan area R1 yang tidak tertib (R1, R2 ... RN-2) dan A New Ordered Area untuk mendapatkan R1 yang tidak tertib, R1, R2 ... RN-2) dan A New Ordered Area untuk mendapatkan R1 R1). Ulangi proses ini sampai jumlah elemen di area yang dipesan adalah N-1, dan seluruh proses penyortiran selesai.
Implementasi Kode JavaScript:
/*Deskripsi metode: heap sortir @param array array untuk diurutkan*/function heapsort (array) {if (object.prototype.toString.call (array) .slice (8, -1) === 'array') {// build heap var heapsize = array.length, temp; untuk (var i = math.floor (heapsize / 2); i> = 0; i--) {heapify (array, i, heapsize); } // heap sort for (var j = heapsize-1; j> = 1; j--) {temp = array [0]; array [0] = array [j]; array [j] = temp; heapify (array, 0, -headsize); }} else {return 'array bukan array!'; }}/ * Deskripsi Metode: Pertahankan properti heap @param arr array @param x array subscript @param len ukuran heap */function heapify (arr, x, len) {if (objek.prototype.toString.call (arr) .slice (8, -1) ===== "x = 2/x = n) 1, terbesar = x, temp; if (l <len && arr [l]> arr [terbesar]) {terbesar = l; } if (r <len && arr [r]> arr [terbesar]) {terbesar = r; } if (terbesar! = x) {temp = arr [x]; arr [x] = arr [terbesar]; arr [terbesar] = temp; heapify (arr, besar, len); }} else {return 'arr bukan array atau x bukan angka!'; }}3) Analisis Algoritma
Kasus Terbaik: t (n) = O (nlogn)
Kasus terburuk: t (n) = o (nlogn)
Rata -rata: t (n) = o (nlogn)
7. Pemesanan
1) Pengantar algoritma
Gabungan penyortiran adalah algoritma penyortiran yang efektif berdasarkan operasi penggabungan. Algoritma ini adalah aplikasi pembagian dan penaklukan yang sangat khas. Gabungkan penyortiran adalah metode penyortiran yang stabil. Gabungkan yang diperintahkan berikutnya untuk mendapatkan urutan yang sepenuhnya diperintahkan; Artinya, buat setiap urutan pertama urutan, dan kemudian buat urutan segmen selanjutnya. Jika dua tabel yang dipesan digabungkan menjadi satu meja yang dipesan, itu disebut gabungan 2 arah.
2) Deskripsi dan implementasi algoritma
Algoritma spesifik digambarkan sebagai berikut:
Bagilah urutan input panjang n menjadi dua setelah panjang n/2;
Kedua selanjutnya diurutkan bersama secara terpisah;
Gabungkan keduanya diurutkan menjadi urutan terakhir yang diurutkan.
Implementasi Kode JavaScript:
fungsi mergeSort (array, p, r) {if (p <r) {var q = math.floor ((p + r) / 2); mergeSort (array, p, q); mergeSort (array, q + 1, r); gabungan (array, p, q, r); }} function gabungan (array, p, q, r) {var n1 = q - p + 1, n2 = r - q, kiri = [], kanan = [], m = n = 0; untuk (var i = 0; i <n1; i ++) {kiri [i] = array [p+i]; } untuk (var j = 0; j <n2; j ++) {kanan [j] = array [q + 1 + j]; } kiri [n1] = kanan [n2] = number.max_value; untuk (var k = p; k <= r; k ++) {if (kiri [m] <= kanan [n]) {array [k] = kiri [m]; M ++; } else {array [k] = kanan [n]; n ++; }}}3) Analisis Algoritma
Kasus Terbaik: t (n) = o (n)
Kasus terburuk: t (n) = o (nlogn)
Rata -rata: t (n) = o (nlogn)
8. Penyortiran ember
1) Pengantar algoritma
Prinsip penyortiran bucket: dengan asumsi bahwa data input didistribusikan secara seragam, data dibagi menjadi sejumlah ember terbatas, dan setiap ember diurutkan secara terpisah (dimungkinkan untuk menggunakan algoritma penyortiran lain atau terus menggunakan penyortiran ember secara rekursif).
2) Deskripsi dan implementasi algoritma
Algoritma spesifik digambarkan sebagai berikut:
Atur array kuantitatif sebagai ember kosong;
Iterasi melalui data input dan masukkan data ke dalam ember yang sesuai satu per satu;
Urutkan setiap ember yang tidak kosong;
Sambungkan data yang diurutkan dari ember kosong.
Implementasi Kode JavaScript:
/*Metode Deskripsi: ember sortir @param array array @param num jumlah ember*/ fungsi bucketsort (array, num) {if (array.length <= 1) {return array; } var len = array.length, buckets = [], result = [], min = max = array [0], regex = '/^[1-9]+[0-9]*$/', ruang, n = 0; num = num || ((num> 1 && regex.test (num))? num: 10); untuk (var i = 1; i <len; i ++) {min = min <= array [i]? min: array [i]; max = max> = array [i]? Max: Array [i]; } space = (maks - min + 1) / num; untuk (var j = 0; j <len; j ++) {var index = math.floor ((array [j] - min) / ruang); if (bucket [index]) {// bucket non -kosong, masukkan sortir var k = bucket [index] .length - 1; while (k> = 0 && buckets [index] [k]> array [j]) {buckets [index] [k + 1] = bucket [index] [k]; K--; } buckets [index] [k + 1] = array [j]; } else {// bucket kosong, inisialisasi ember [index] = []; ember [indeks] .push (array [j]); }} while (n <num) {result = result.concat (bucket [n]); n ++; } hasil pengembalian; }3) Analisis Algoritma
Dalam kasus terbaik penyortiran ember, waktu linier O (n), kompleksitas waktu penyortiran ember tergantung pada kompleksitas waktu penyortiran data antara ember, karena kompleksitas waktu dari bagian lain adalah O (n). Jelas, semakin kecil ember dibagi, semakin sedikit data ember, semakin sedikit waktu yang diperlukan untuk mengurutkannya. Tetapi konsumsi ruang yang sesuai akan meningkat.
9. Menghitung penyortiran
1) Pengantar algoritma
Penghitungan Sort adalah algoritma penyortiran yang stabil. Hitungan Penyortiran menggunakan array tambahan C, di mana elemen i-th adalah jumlah elemen dengan nilai yang sama dengan I di array A untuk disortir. Kemudian, menurut Array C, elemen -elemen dalam A diatur ke posisi yang benar. Itu hanya bisa mengurutkan bilangan bulat.
2) Deskripsi dan implementasi algoritma
Algoritma spesifik digambarkan sebagai berikut:
Temukan elemen terbesar dan terkecil dalam array untuk disortir;
Hitung berapa kali setiap elemen dengan nilai i dalam array muncul dan simpan ke item ke-i array c;
Mengumpulkan semua jumlah (mulai dari elemen pertama dalam C, setiap item dan item sebelumnya ditambahkan);
Reverse Fill Target Array: Tempatkan setiap elemen I dalam item C (i) dari array baru, dan kurangi C (i) dengan 1 untuk setiap elemen.
Implementasi Kode JavaScript:
Function CountingSort (array) {var len = array.length, b = [], c = [], min = max = array [0]; untuk (var i = 0; i <len; i ++) {min = min <= array [i]? min: array [i]; max = max> = array [i]? Max: Array [i]; C [array [i]] = c [array [i]]? C [array [i]] + 1: 1; } untuk (var j = min; j <max; j ++) {c [j + 1] = (c [j + 1] || 0) + (c [j] || 0); } untuk (var k = len - 1; k> = 0; k--) {b [c [array [k]] - 1] = array [k]; C [array [k]]-; } return b; }3) Analisis Algoritma
Ketika elemen input adalah n bilangan bulat antara 0 dan k, waktu berjalannya adalah O (n + k). Penyortiran penghitungan bukanlah penyortiran perbandingan, dan kecepatan penyortiran lebih cepat daripada algoritma penyortiran perbandingan apa pun. Karena panjang array C yang digunakan untuk menghitung tergantung pada kisaran data dalam array yang akan diurutkan (sama dengan perbedaan antara nilai maksimum dan minimum array yang akan diurutkan ditambah 1), ini membuat penyortiran hitungan membutuhkan banyak waktu dan memori untuk array dengan rentang data yang besar.