Saya telah terpapar dengan berbagai dasar algoritma sejak saya mempelajari struktur data, tetapi saya belum pernah mempraktikkannya sejak saya menyelesaikan ujian. Ketika saya sedang berkembang, saya juga memeriksa ketika saya menggunakannya. Sekarang saya sedang belajar JavaScript. Saya akan mengambil waktu ini untuk mengatur berbagai algoritma dasar dan menulis kode dalam sintaks JS dan PHP masing -masing.
1. Penyortiran gelembung
Prinsip: Bandingkan angka yang berdekatan berpasangan dan pertukarannya secara berurutan dari kecil ke besar atau besar hingga kecil. Setelah perjalanan, angka terbesar atau terkecil ditukar dengan digit terakhir, dan kemudian membandingkan dan menukarnya dari awal sampai digit kedua hingga terakhir berakhir.
Kompleksitas Waktu: Kasus Rata -rata: O (N2) Kasus Terbaik: O (N) Kasus Terburuk: O (N2)
Kompleksitas Ruang: O (1)
Stabilitas: Stabil
// sintaks javascript var array = [23,0,32,45,56,75,43,0,34]; untuk (var i = 0; i <array.length; i ++) {var issort = true; untuk (var j = 0; j <array.length - 1 - i; j ++) {if (array [j]> array [j+1]) {issort = false; var temp = array [j]; array [j] = array [j + 1]; array [j + 1] = temp; }} if (isSort) {break; }} console.log (array); <? PHP $ array = [23,0,32,45,56,75,43,0,34]; untuk ($ i = 0; $ i <count ($ array); $ i ++) {$ issort = true; untuk ($ j = 0; $ j <count ($ array) - 1; $ j ++) {if ($ array [$ j]> $ array [$ j+1]) {$ issort = false; $ temp = $ array [$ j]; $ array [$ j] = $ array [$ j + 1]; $ array [$ j + 1] = $ temp; }} if ($ isSort) {break; }} var_dump ($ array);?>2. Penyortiran pilihan sederhana
Prinsip: Dengan membandingkan kata kunci NI, pilih catatan dengan kata kunci terkecil dari catatan N-I+1, dan pertukarannya dengan I (1 <= i <= n) catatan. Kinerja penyortiran pilihan sederhana sedikit lebih baik daripada penyortiran gelembung.
Kompleksitas Waktu: Kasus Rata -rata: O (N2) Kasus Terbaik: O (N) Kasus Terburuk: O (N2)
Kompleksitas Ruang: O (1)
Stabilitas: tidak stabil
// javascript var array = [23,0,32,45,56,75,43,0,34]; untuk (var i = 0; i <array.length - 1; i ++) {var pos = i; untuk (var j = i+1; j <array.length; j ++) {if (array [j] <array [pos]) {pos = j; }} var temp = array [i]; array [i] = array [pos]; array [pos] = temp; } console.log (array); <? PHP $ array = [23,0,32,45,56,75,43,0,34]; untuk ($ i = 0; $ i <count ($ array); $ i ++) {$ pos = $ i; untuk ($ j = $ i+1; $ j <count ($ array); $ j ++) {if ($ array [$ j] <$ array [$ pos]) {$ pos = $ j; }} $ temp = $ array [$ i]; $ array [$ i] = $ array [$ pos]; $ array [$ pos] = $ temp; } var_dump ($ array);?>3. Langsung masukkan Sort
Prinsip: Masukkan catatan ke tabel yang dipesan diurutkan, sehingga mendapatkan tabel yang dipesan baru dengan 1 kenaikan catatan. Artinya, perlakukan rekaman pertama dari urutan sebagai setelah yang dipesan, dan kemudian masukkan satu per satu dari catatan kedua sampai seluruh urutan dipesan. Kinerja yang lebih baik daripada metode gelembung dan penyortiran seleksi
Kompleksitas Waktu: Kasus Rata -rata: O (N2) Kasus Terbaik: O (N) Kasus Terburuk: O (N2)
Kompleksitas Ruang: O (1)
Stabilitas: Stabil
// javascript var array = [23,0,32,45,56,75,43,0,34]; untuk (var j = 0; j <array.length; j ++) {var key = array [j]; var i = j - 1; while (i> -1 && array [i]> key) {array [i + 1] = array [i]; i = i - 1; } array [i + 1] = key; } console.log (array); <? php // langsung masukkan sortir $ array = [23,0,32,45,56,75,43,0,34]; untuk ($ i = 0; $ i <count ($ array); $ i ++) {$ key = $ array [$ i]; $ j = $ i - 1; while ($ j> -1 && $ array [$ j]> $ key) {$ array [$ j +1] = $ array [$ j]; $ j = $ J - 1; } $ array [$ j + 1] = $ key; } var_dump ($ array);?>4. Sortir Cepat
Prinsip: Melalui penyortiran, data yang akan diurutkan dibagi menjadi dua bagian independen, dan semua data sebagian lebih kecil dari semua data di bagian lain, dan kemudian dua bagian data dengan cepat diurutkan sesuai dengan metode ini. Seluruh proses penyortiran dapat dilakukan secara rekursif untuk mencapai seluruh data menjadi urutan yang dipesan.
Kompleksitas Waktu: Kasus Rata -rata: O (NLOG2N) Kasus Terbaik: O (NLOG2N) Kasus terburuk: O (N2)
Kompleksitas Ruang: O (NLOG2N)
Stabilitas: tidak stabil
// JavaScript cepat sortir var array = [23,0,32,45,56,75,43,0,34]; var quicksort = function (arr) {if (arr.length <= 1) {return arr; } // Periksa jumlah elemen dalam array, jika kurang dari atau sama dengan 1, itu akan dikembalikan. var pivotIndex = math.floor (arr.length/2); // var pivot = arr.splice (pivotIndex, 1) [0]; // pilih "benchmark" (pivot) dan pisahkan dari satu array asli, var kiri = []; // tentukan dua array kosong untuk menyimpan dua subset dari satu kiri dan var kanan = []; untuk (var i = 0; i <arr.length; i ++) // transweep array, masukkan elemen lebih kecil dari "tolok ukur" ke dalam subset di sebelah kiri, dan elemen yang lebih besar dari tolok ukur ke dalam subset di sebelah kanan. {if (arr [i] <pivot) {left.push (arr [i]); } else {right.push (arr [i]); }} return quicksort (kiri) .concat ([pivot], quicksort (kanan)); // Ulangi proses ini secara terus menerus untuk mendapatkan array yang diurutkan. }; var newarray = quicksort (array); console.log (newarray); <? PHP $ array = [23,0,32,45,56,75,43,0,34]; function quick_sort ($ arr) {// Pertama tentukan apakah Anda perlu melanjutkan $ panjang = hitung ($ arr); if ($ length <= 1) {return $ arr; } $ base_num = $ arr [0]; // Pilih penggaris untuk memilih elemen pertama // inisialisasi dua array $ left_array = array (); // $ right_array kurang dari penggaris = array (); // untuk ($ i = 1; $ i <$ length; $ i ++) {// mentransfer semua elemen kecuali penguasa dan penguasa $ ke dalam panjang dua; $ arr [$ i]) {// dimasukkan ke dalam array kiri $ left_array [] = $ arr [$ i]; } else {// dimasukkan ke kanan $ right_array [] = $ arr [$ i]; }} // Kemudian metode penyortiran yang sama untuk masing -masing array kiri dan kanan // memanggil fungsi ini secara rekursif dan merekam hasilnya $ left_array = quick_sort ($ left_array); $ right_array = quick_sort ($ right_array); // gabungkan penguasa kiri ke pengembalian kanan array_merge ($ left_array, array ($ base_num), $ right_array); } $ newArray = quick_sort ($ array); var_dump ($ newarray);?>5. Bukit Sort
Prinsip: Pertama, bagi seluruh urutan rekaman yang akan diurutkan menjadi beberapa sub-sekuens untuk penyisipan dan penyortiran langsung. Ketika catatan di seluruh urutan "pada dasarnya dipesan", lalu masukkan dan urutkan seluruh catatan secara berurutan. .
Kompleksitas Waktu: Kasus Rata -rata: O (N√N) Kasus Terbaik: O (NLOG2N) Kasus terburuk: O (N2)
Kompleksitas Ruang: O (1)
Stabilitas: tidak stabil
// JavaScript Hill Sort Var Array = [23,0,32,45,56,75,43,0,34]; var shellsort = function (arr) {var length = arr.length; var h = 1; while (h <panjang/3) {h = 3*h+1; // atur interval} while (h> = 1) {for (var i = h; i <panjang; i ++) {untuk (var j = i; j> = h && arr [j] <arr [jh]; j- = h) {var var suh = arr [jh]; arr [jh] = arr [j]; arr [j] = temp; }} h = (h-1)/3; } return arr; } var newArray = shellsort (array); console.log (newarray); <? php // hill sort $ array = [23,0,32,45,56,75,43,0,34]; function shellsort ($ arr) {$ length = count ($ arr); $ h = 1; while ($ h <$ length/3) {$ h = 3*$ h+1; // Set Interval} sementara ($ h> = 1) {untuk ($ i = $ h; $ i <$ length; $ i ++) {untuk ($ j = $ $ J] = $ h && $ ARR [$ j] <$ arr [$ j- $ h]; $ J-$ h && $ ARR [$ J] <$ arr [$ J- $ h]; $ arr [$ j- $ h] = $ arr [$ j]; $ arr [$ j] = $ temp; }} $ h = ($ h-1)/3; } return $ arr; } $ newArray = shellsort ($ array); var_dump ($ newarray)?>6. Pemesanan
Prinsip: Dengan asumsi bahwa urutan awal berisi catatan N, itu dapat dianggap sebagai N yang dipesan berikutnya, masing -masing secepatnya memiliki panjang 1, dan kemudian digabungkan dalam pasangan untuk mendapatkan (bilangan bulat terkecil tidak kurang dari n/2) yang dipesan dengan panjang dengan panjang 2 atau 1, dan digabungkan dalam pasangan ... ulangi dengan cara ini sampai urutan yang diperintahkan dengan panjang n diperoleh. Diperoleh.
Kompleksitas Waktu: Kasus Rata -rata: O (NLOG2N) Kasus Terbaik: O (NLOG2N) Kasus terburuk: O (NLOG2N)
Kompleksitas Ruang: O (1)
Stabilitas: Stabil
// JavaScript menggabungkan fungsi penyortiran isArray1 (arr) {if (object.prototype.toString.call (arr) == '[objek array]') {return true; } else {return false; }} function gabungan (kiri, kanan) {var result = []; if (! isArray1 (kiri)) {kiri = [kiri]; } if (! isArray1 (kanan)) {right = [kanan]; } while (left.length> 0 && right.length> 0) {if (kiri [0] <kanan [0]) {result.push (left.shift ()); } else {result.push (right.shift ()); }} return result.concat (kiri) .concat (kanan); } function mergeSort (arr) {var len = arr.length; var lim, work = []; var i, j, k; if (len == 1) {return arr; } untuk (i = 0; i <len; i ++) {work.push (arr [i]); } work.push ([]); untuk (lim = len; lim> 1;) {// lim adalah panjang pengelompokan untuk (j = 0, k = 0; k <lim; j ++, k = k+2) {work [j] = gabungan (kerja [k], kerja [k+1]); } bekerja [j] = []; lim = math.floor ((lim+1)/2); } return work [0]; } var array = [23,0,32,45,56,75,43,0,34]; console.log (mergeSort (array)); <? php // Memahami fungsi penyortiran mergeSort (& $ arr) {$ len = count ($ arr); // menemukan panjang array msort ($ arr, 0, $ len-1); } // Program yang benar -benar mengimplementasikan fungsi penyortiran gabungan msort (& $ arr, $ kiri, $ kanan) {if ($ kiri <$ kanan) {// menunjukkan bahwa ada 1 elemen tambahan dalam selanjutnya, maka perlu untuk membagi, mengurutkan secara terpisah, gabungan // Hitung posisi split, panjang /2 pergi ke seluruh $ center = lantai $ $ $ $) ($ $ $)) /HIDUP) /2), panjang /2 pergi ke keseluruhan $ center = lantai $ $ $ $)) /HIDUP) /2); // panggilan rekursif mengurutkan sisi kiri lagi: msort ($ arr, $ kiri, $ center); // panggilan rekursif untuk mengurutkan sisi kanan lagi msort ($ arr, $ center+1, $ right); // gabungkan hasil sortir mergearray ($ arr, $ kiri, $ center, $ kanan); }} // Gabungkan dua nomor yang dipesan ke dalam fungsi array yang dipesan mergearray (& $ arr, $ kiri, $ center, $ kanan) {// atur dua posisi posisi awal $ a_i = $ kiri; $ b_i = $ center+1; while ($ a_i <= $ center && $ b_i <= $ right) {// Ketika tidak ada array A atau array B melintasi batas jika ($ arr [$ a_i] <$ arr [$ b_i]) {$ temp [] = $ arr [$ a_i ++]; } else {$ temp [] = $ arr [$ b_i ++]; }} // menilai apakah semua elemen dalam array A digunakan. Jika tidak, masukkan semua elemen dalam array c: while ($ a_i <= $ center) {$ temp [] = $ arr [$ a_i ++]; } // menilai apakah semua elemen dalam array B digunakan. Jika tidak, masukkan semua elemen dalam array c: while ($ b_i <= $ right) {$ temp [] = $ arr [$ b_i ++]; } // Tulis bagian yang diurutkan dalam $ ARRC menjadi $ ARR: untuk ($ i = 0, $ len = hitungan ($ temp); $ i <$ len; $ i ++) {$ arr [$ left+$ i] = $ temp [$ i]; }} $ arr = array (23,0,32,45,56,75,43,0,34); Mergesort ($ ARR); var_dump ($ arr);?>7. Heap Sorting
Prinsip: Heap Sorting adalah metode penyortiran menggunakan heap. Ide dasarnya adalah: untuk membangun urutan yang akan diurutkan menjadi tumpukan atas yang besar. Pada saat ini, nilai maksimum dari seluruh urutan adalah simpul root bagian atas heap. Hapus (pada kenyataannya, itu adalah untuk menukarnya dengan elemen akhir dari array heap, dan elemen akhir adalah nilai maksimum), dan kemudian merekonstruksi urutan N-1 yang tersisa menjadi tumpukan, sehingga nilai submaksimum dari elemen N akan diperoleh. Ini akan menghasilkan eksekusi berulang dan urutan yang dipesan dapat diperoleh.
Kompleksitas Waktu: Kasus Rata -rata: O (NLOG2N) Kasus Terbaik: O (NLOG2N) Kasus terburuk: O (NLOG2N)
Kompleksitas Ruang: O (1)
Stabilitas: tidak stabil
// JavaScript Heap Sort Var Array = [23,0,32,45,56,75,43,0,34]; function heapsort (array) {for (var i = math.floor (array.length / 2); i> = 0; i--) {heapadjust (array, i, array.length-1); // Bangun array array ke dalam tumpukan atas besar} untuk (i = array.length-1; i> = 0; i--) {/*Swap node root*/var temp = array [i]; array [i] = array [0]; array [0] = temp; /*Array yang tersisa terus dibangun ke dalam tumpukan atas besar*/ heapadjust (array, 0, i - 1); } return array; } Fungsi heapadjust (array, start, max) {var temp = array [start]; // temp adalah nilai node root untuk (var j = 2 * start; j <max; j * = 2) {if (j <max && array [j] <array [j+1]) {if if (j <max && array [j] <array [j+1]) {if if (j <max && array [j] <array [j+1]) {if if (j <max && array [j] <array [j+1]) {ife (j <max && array [j] <array [j+1]) {J if gets dari Subscript dari Children Older ++ J; } if (temp> = array [j]) break; array [start] = array [j]; mulai = j; } array [start] = temp; } var newArray = heapsort (array); console.log (newarray); <? php // heap sortir function heapsort (& $ arr) {#initheap ($ arr, 0, count ($ arr) - 1); #Start menukar node kepala dan ekor, dan mengurangi satu node ujung sekaligus dan menyesuaikan tumpukan sampai ada elemen yang tersisa untuk ($ end = count ($ arr)-1; $ end> 0; $ end--) {$ temp = $ arr [0]; $ arr [0] = $ arr [$ end]; $ arr [$ end] = $ temp; Ajustnodes ($ arr, 0, $ end - 1); }} #Initialize tumpukan maksimum, mulailah dari simpul non-daun terakhir, dan simpul non-daun terakhir diberi nomor sebagai panjang array/2 round down function initheap (& $ arr) {$ len = count ($ arr); untuk ($ start = lantai ($ len / 2) - 1; $ start> = 0; $ start--) {ajustnodes ($ arr, $ start, $ len - 1); }}#Custonnodes#@param $ arr array untuk disesuaikan#@param $ mulai koordinat simpul induk yang akan disesuaikan#@param $ end koordinat node akhir yang akan disesuaikan fungsi ajustnodes (& $ arr, $ start, $ end) {$ maxinx = $ start; $ len = $ end + 1; #Panjang bagian yang akan disesuaikan $ leftchildinx = ($ start + 1) * 2 - 1; #Left anak koordinat $ rightchildinx = ($ start + 1) * 2; #Right Child Coordinate #Jika bagian yang akan disesuaikan memiliki anak kiri jika ($ leftchildinx + 1 <= $ len) {#get koordinat simpul minimum jika ($ arr [$ maxinx] <$ arr [$ leftchildinx]) {$ maxinx = $ leftchildinx; } #Jika bagian yang akan disesuaikan memiliki simpul anak yang tepat jika ($ rightChildinx + 1 <= $ len) {if ($ arr [$ maxinx] <$ arr [$ rightChildinx]) {$ maxinx = $ rightChildinx; }}} #Swap node induk dan simpul maksimum if ($ start! = $ Maxinx) {$ temp = $ arr [$ start]; $ arr [$ start] = $ arr [$ maxinx]; $ arr [$ maxinx] = $ temp; #Jika node anak setelah pertukaran memiliki node anak, lanjutkan untuk menyesuaikan IF (($ maxinx + 1) * 2 <= $ len) {ajustnodes ($ arr, $ maxinx, $ end); }}} $ arr = array (23,0,32,45,56,75,43,0,34); heapsort ($ arr); var_dump ($ arr);?>8. Penyortiran Kardinalitas
Prinsip: Potong bilangan bulat menjadi angka yang berbeda dengan digit, dan kemudian bandingkan secara terpisah dengan setiap digit. Karena bilangan bulat juga dapat mengekspresikan string (seperti nama atau tanggal) dan bilangan titik mengambang dalam format tertentu, pemilahan radix tidak hanya digunakan untuk bilangan bulat.
Kompleksitas Waktu: Kasus Rata -rata: O (D (R+N)) Kasus Terbaik: O (D (N+RD)) Kasus terburuk: O (D (R+N)) R: Kardinalitas kata kunci D: Panjang N: Jumlah kata kunci
Kompleksitas Ruang: O (RD+N)
Stabilitas: Stabil
<? PHP #Blassortting, di sini hanya bilangan bulat positif yang diurutkan. Adapun angka negatif dan angka titik mengambang, diperlukan komplemen. Anda tertarik untuk mempelajari #countting sort #@param $ array untuk diurutkan #@param $ digit_num sesuai dengan jumlah fungsi digit Counting_sort (& $ arr, $ digit_num = false) {if ($ digit_num! == false) {#jika parameter $ digit_num tidak kosong, sortir nomornya menurut nomor tersebut menurut angka menurut nomor tersebut menurut nomor tersebut menurut nomor tersebut menurut nomor tersebut menurut nomor tersebut menurut nomor tersebut menurut nomor tersebut menurut nomor tersebut menurut nomor tersebut menurut nomor tersebut menurut nomor tersebut menurut nomor tersebut menurut nomor tersebut. Menurut nomor tersebut, angka Digit $ Digit, hitung ($ arr); $ i ++) {$ arr_temp [$ i] = get_specific_digit ($ arr [$ i], $ digit_num); }} else {$ arr_temp = $ arr; } $ max = max ($ arr); $ time_arr = array (); #Storage array elemen kejadian#inisialisasi array kejadian untuk ($ i = 0; $ i <= $ max; $ i ++) {$ time_arr [$ i] = 0; } #Statize kejadian setiap elemen untuk ($ i = 0; $ i <count ($ arr_temp); $ i ++) {$ time_arr [$ arr_temp); $ i ++) {$ time_arr [$ arr_temp [$ i]] ++; } #Statifikasi kejadian setiap elemen yang lebih kecil atau sama dengan itu untuk ($ i = 0; $ i <count ($ time_arr) - 1; $ i ++) {$ time_arr [$ i +1] += $ time_arr [$ i]; } #Sort array menggunakan jumlah kejadian untuk ($ i = count ($ arr) - 1; $ i> = 0; $ i--) {$ sorted_arr [$ time_arr [$ arr_temp [$ i]] - 1] = $ arr [$ i]; $ time_arr [$ arr_temp [$ i]]-; } $ arr = $ sorted_arr; ksort ($ arr); #Ignore Kehilangan efisiensi penyortiran kunci kali ini} #kali jumlah bit dari fungsi nomor tertentu get_digit ($ number) {$ i = 1; while ($ number> = pow (10, $ i)) {$ i ++; } return $ i; } #get nomor angka i -th dari angka dari fungsi satu digit get_specific_digit ($ num, $ i) {if ($ num <pow (10, $ i - 1)) {return 0; } Return floor ($ num % pow (10, $ i) / pow (10, $ i - 1)); } #Black sortting, hitung penyortiran sebagai fungsi proses sub-sorting Radix_sort (& $ arr) {#first Temukan digit terbesar di array $ max = max ($ arr); $ max_digit = get_digit ($ max); untuk ($ i = 1; $ i <= $ max_digit; $ i ++) {counting_sort ($ arr, $ i); }} $ arr = array (23,0,32,45,56,75,43,0,34); radix_sort ($ arr); var_dump ($ arr);?>Di atas adalah semua konten artikel ini. Saya berharap ini akan membantu untuk pembelajaran semua orang dan saya harap semua orang akan lebih mendukung wulin.com.