Sortir Gelembung
Prinsip gelembung adalah membuat elemen terbesar atau elemen terkecil "float"
Masukkan sortir, pilih sortir, sortir cepat, bubble sort adalah jenis perbandingan
Ide
Bandingkan dua angka yang berdekatan satu per satu, letakkan desimal di depan dan angka besar di belakang.
Langkah1: Bandingkan angka pertama dan kedua, letakkan desimal sebelum dan angka besar setelahnya. Bandingkan angka kedua dan angka ketiga, letakkan desimal sebelum dan sesudah angka besar, lanjutkan seperti ini sampai dua angka terakhir dibandingkan, letakkan desimal sebelum dan sesudah angka besar.
Langkah2: Pada perjalanan kedua: masih mulai dari logaritma pertama (karena mungkin karena pertukaran angka kedua dan angka ketiga, angka pertama tidak lagi lebih kecil dari angka kedua), letakkan desimal sebelum dan sesudah meletakkan angka besar, bandingkan sampai angka kedua dari belakang (posisi pertama sudah menjadi yang terbesar pada posisi kedua dari belakang). Pada akhir perjalanan kedua, angka maksimum baru diperoleh pada posisi kedua dari belakang (sebenarnya angka terbesar kedua di seluruh urutan).
Jika ini berlanjut, ulangi proses di atas sampai penyortiran akhirnya selesai.
Karena desimal selalu ditempatkan ke depan dan jumlah besar ditempatkan ke belakang selama proses penyortiran, yang setara dengan munculnya gelembung, itu disebut penyortiran gelembung.
Efek animasi penyortiran gelembung
Implementasi: Kode ini relatif sederhana dan merupakan kode paling dasar dan dasar dalam algoritma. . .
Tiga hal yang perlu diperhatikan
1. Metode pertukaran kelas dapat diselesaikan dalam JavaScript dengan a = [b, b = a] [0].
mengganti
Salinan kode adalah sebagai berikut:
var, a, b, temp
temp = a;
a = b;
b = temp
Metode pertukaran ini
2. Perhatikan cache variabel loop, di mana array.length di -cache
3. Perhatikan loop tertanam, yaitu membandingkan dari nomor pertama dengan angka terakhir ke -n, dan n adalah angka langkah perbandingan
function bubbleSort(array) {var l=array.length;for (var i = 0; i < l; i++) {//The number of steps compared is the length of the array for (var j = 0; j < li; j++) {//The number of inline exchanges is compared from the first number to the total length of the last -n numbers, n is the comparison step if (array[j] < array[j - 1]) {array [j] = [array [j - 1], array [j - 1] = array [j]] [0] // elemen swap di sini}} untuk (var k = 0; k <l; k ++) {console.log (array [k]+"); [6,54,6,22,5,7,8,2,34]; Bubblesort (A);Efek animasi
Sort Penyisipan
Ini sangat sederhana, ini adalah langkah bagi kami untuk menyentuh dan memasukkan kartu!
Ide:
1 Pertama, katakanlah kami menyentuh kartu, dan semua kartu di tangan kami diatur ke kosong = [] menyentuh dorongan (arr [0])
2 Keluarkan kartu berikutnya, atur ke, pindai dari belakang ke depan di semua kartu kami kosong (sudah diurutkan)
3 Jika kartu di tangan Anda kosong [kosong.length-n] (diurutkan) lebih besar dari elemen baru, pindahkan kartu ke posisi berikutnya (lepaskan ruang) kosong [kosong.length-n] = kosong [kosong.length-n+1]
4Repeat Langkah 3 Sampai kartu yang diurutkan kosong [kosong.length-n] kurang dari atau sama dengan a
5 Masukkan ke posisi ini kosong [kosong.length-n] = a
6 Ulangi Langkah 2
Namun, kode JavaScript masih agak sulit untuk diimplementasikan, kode ini sebagai berikut:
function insert (arr) {var l = arr.length; var kosong = []; // array kosong, menunjukkan tangan kita kosong. if (arr [i]> empt [empt.length - 1]) {empt [empt.length] = arr [i]} // Jika lebih besar dari array yang dipesan kosong, letakkan langsung ke ujung untuk (var j = empt.length; j> 0 && arr [i] <kosong [j - 1]; j--) {// Bandingkan dengan Nilai Maxiume dengan Arr di Arr di Arr di Arr di Arr di urutan di Arr di urutan di Arr di Arr. Ketika arr <sedikit array yang dipesan, tidak perlu memindahkannya. kosong [j] = kosong [j - 1]; // pindahkan kosong [j - 1] = arr [i]; // Letakkan nilainya ke posisi kosong} // console.log (kosong)} return kosong}Maka titik pengetahuan yang lebih penting di sini adalah simbol &&, yang berarti "dan", yaitu, kondisi di kedua sisi harus dipenuhi sebelum ekspresi ditetapkan.
Simbol && juga dapat menggantikan jika, misalnya, if (a) {fun ()} sama dengan a && b
Poin yang sangat penting lainnya
Dengan asumsi array adalah ARR, maka "item terakhir" adalah arr [arr.length-1].
Urutkan animasi
Jenis seleksi
Ini juga merupakan algoritma penyortiran yang sederhana.
Ide:
Temukan elemen terkecil - lempar ke dalam array - temukan yang kecil lagi - lempar ke dalam array, dan sebagainya.
Pertama, temukan elemen terkecil di array yang tidak disortir. Metode yang Anda temukan dapat menggunakan cara penilaian dan penugasan berkelanjutan, yaitu,: Biarkan array elemen pertama [0] dari array menjadi elemen terkecil, maka nomor urutan "elemen minimum" dalam array adalah 0.
Kemudian peroleh di atas array. Jika elemen kedua dari array lebih kecil dari itu, maka elemen kedua adalah elemen terkecil dan perbarui "0" ke "1".
Setelah melintasi, kita tahu bahwa subskrip elemen terkecil dalam seri ini adalah "n"; itu diambil dan disimpan pada posisi awal dari urutan penyortiran (array [n])
Kemudian, terus mencari elemen terkecil dari elemen yang tidak disortir, dan kemudian letakkan di akhir urutan yang diurutkan. Perhatikan bahwa subskrip traversal dimulai dari 1 saat ini. Karena kami telah memilih elemen terkecil.
Dan seterusnya sampai semua elemen diurutkan.
Fungsi SelectSort (array) {var min; var l = array.length; // Panjang cache untuk (var i = 0; i <l; i ++) {// mulai loop, loop 1 kali secara total, dan Anda dapat menemukan elemen l min = i;/ (Array [min]> array [j]) // menilai apakah min = j; // memperbarui subskrip "minimum"} if (min! = i) {// karena di sini, karena beroperasi dalam array yang sama, Anda dapat secara langsung bertukar elemen. Misalnya, item pertama dari array adalah saya, lalu saya menemukan bahwa elemen terkecil adalah array [mnt], jadi saya perlu menukar min ini dengan i. Dan sebagainya. array [i] = [array [min], array [min] = array [i]] [0]; // swap elemen}} return array;}Yang masih dicatat di sini adalah metode penulisan pertukaran array [i] = [array [min], array [min] = array [i]] [0]
Mudah untuk bertukar array [i] dan array [min] ~
Urutkan animasi
Sortir cepat
Jenis cepat adalah algoritma penyortiran yang paling kuat saat ini, yang memanfaatkan gagasan rekursi.
Ide
Memilih elemen dari array disebut "tolok ukur". Ini dapat dipilih secara langsung menggunakan panjang/2
Iterasi melalui array, semua elemen dengan nilai referensi yang lebih kecil ditempatkan di depan referensi, dan semua elemen dengan nilai referensi lebih besar ditempatkan di belakang referensi (angka yang sama dapat digunakan di kedua sisi). Dalam istilah awam, pria itu berdiri di sebelah kiri dan wanita itu berdiri di sebelah kanan. .
Kemudian kami mendapatkan array array = array larray yang terdiri dari bagian yang lebih kecil dari benchmark + array rarray yang terdiri dari bagian -bagian yang lebih besar dari tolok ukur.
Maka kita hanya perlu proses "sama" Larray dan Rarray ~
Ini membutuhkan penggunaan penulisan rekursi. Setelah diproses, Larray dibagi menjadi tolok ukur Larray, yang lebih kecil dari tolok ukur Larray dan lebih besar dari tolok ukur Larray. .
Kemudian kami terus melakukan sesuatu, pria itu berdiri di sebelah kiri dan wanita itu berdiri di sebelah kanan. .
Sampai kita menemukan bahwa panjang Larray telah menjadi 1, yang tidak cukup untuk dibagi lagi, kita pikir penyortiran sudah berakhir.
function quicksort (arr) {var l = arr.length; // array length if (arr.length <= 1) {return arr}; // Jika panjang larray dan rarray yang kita dapatkan lebih kecil dari 1, maka tidak perlu berbaris ~ var num = math.floor (arr.length/2); // Pilih nomor di tengah array. Perhatikan bahwa panjang/2 belum tentu bilangan bulat. Use Math.floor to round var numValue = arr.splice(num, 1)[0];//Use the splice method to take an element, pay attention to the syntax var left = [];//Create the left reference container var right = [];//Create the right reference container for (var i = 0; i < l; i += 1) {//Start traverse the array arr[i] < numValue ? left.push (arr [i]): kanan.push (arr [i]); // Pria itu berdiri di sebelah kiri dan wanita itu berdiri di sebelah kanan. . } return quicksort (kiri) .concat ([numValue], quicksort (kanan)) // secara rekursif, terus beroperasi pada array kiri dan kanan. }Efek animasi:
Perhatikan di sini bahwa meskipun arr.splice (num, 1) hanya menggambar satu angka, hasil sambungan juga merupakan array, yang membutuhkan [0], jika tidak hasilnya akan anehnya sekelompok array array (1). . .
Referensi sambungan: //www.vevb.com/w3school/js/jsref_splice.htm
Math.floor adalah referensi untuk objek matematika //www.vevb.com/w3school/js/js_obj_math.htm
Apa itu rekursi: http://baike.baidu.com/view/96473.htm
Selain penyortiran cepat, empat algoritma di atas semuanya adalah algoritma penyortiran sederhana, dan keempat algoritma ini sangat sering diambil selama wawancara ~
Masih penting untuk menekankan di sini bahwa algoritma di atas menggunakan banyak pengetahuan yang relevan tentang loop dan array, jadi Anda harus menghafalnya!