從學習數據結構開始就接觸各種算法基礎，但是自從應付完考試之後就再也沒有練習過，當在開發的時候也是什麼時候使用什麼時候去查一下，現在在學習JavaScript，趁這個時間再把各種基礎算法整理一遍，分別以JS和PHP語法的方式編寫代碼。
1.冒泡排序
原理：臨近的數字兩兩進行比較,按照從小到大或者從大到小的順序進行交換,這樣一趟過去後,最大或最小的數字被交換到了最後一位,然後再從頭開始進行兩兩比較交換,直到倒數第二位時結束
時間複雜度：平均情況：O（n2） 最好情況：O（n） 最壞情況：O（n2）
空間複雜度： O（1）
穩定性：穩定
//JavaScript語法var array = [23,0,32,45,56,75,43,0,34]; for(var i = 0; i < array.length; i++) { var isSort = true; for(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]; for($i = 0; $i < count($array); $i++) { $isSort = true; for($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.簡單選擇排序
原理：通過ni次關鍵字之間的比較,從n-i+1 個記錄中選擇關鍵字最小的記錄,並和第i(1<=i<=n)個記錄交換簡單選擇排序的性能要略優於冒泡排序
時間複雜度:平均情況：O（n2） 最好情況：O（n） 最壞情況：O（n2）
空間複雜度： O（1）
穩定性：不穩定
//JavaScript var array = [23,0,32,45,56,75,43,0,34]; for(var i = 0; i < array.length - 1; i++) { var pos = i; for(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]; for($i = 0; $i < count($array); $i++) { $pos = $i; for($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.直接插入排序
原理：將一個記錄插入到已排序好的有序表中，從而得到一個新，記錄數增1的有序表。即：先將序列的第1個記錄看成是一個有序的子序列，然後從第2個記錄逐個進行插入，直至整個序列有序為止。 比冒泡法和選擇排序的性能要更好一些
時間複雜度：平均情況：O（n2） 最好情況：O（n） 最壞情況：O（n2）
空間複雜度： O（1）
穩定性：穩定
//JavaScript var array = [23,0,32,45,56,75,43,0,34]; for(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 //直接插入排序$array = [23,0,32,45,56,75,43,0,34]; for($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.快速排序
原理：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。
時間複雜度:平均情況：O（nlog2n） 最好情況：O（nlog2n） 最壞情況：O（n2）
空間複雜度： O（nlog2n）
穩定性：不穩定
//JavaScript 快速排序var array = [23,0,32,45,56,75,43,0,34]; var quickSort = function(arr) { if (arr.length <= 1) { return arr; }//檢查數組的元素個數，如果小於等於1，就返回。 var pivotIndex = Math.floor(arr.length / 2);// var pivot = arr.splice(pivotIndex,1)[0];//選擇"基準"（pivot），並將其與原數組分離， var left = [];//定義兩個空數組，用來存放一左一右的兩個子集var right = []; for (var i = 0; i < arr.length; i++)//遍歷數組，小於"基準"的元素放入左邊的子集，大於基準的元素放入右邊的子集。 { if (arr[i] < pivot) { left.push(arr[i]); } else { right.push(arr[i]); } } return quickSort(left).concat([pivot], quickSort(right));//使用遞歸不斷重複這個過程，就可以得到排序後的數組。 }; var newArray=quickSort(array); console.log(newArray); <?php $array = [23,0,32,45,56,75,43,0,34]; function quick_sort($arr) { //先判斷是否需要繼續進行$length = count($arr); if($length <= 1) { return $arr; } $base_num = $arr[0];//選擇一個標尺選擇第一個元素//初始化兩個數組$left_array = array();//小於標尺的$right_array = array();//大於標尺的for($i=1; $i<$length; $i++) { //遍歷除了標尺外的所有元素，按照大小關係放入兩個數組內if($base_num > $arr[$i]) { //放入左邊數組$left_array[] = $arr[$i]; } else { //放入右邊$right_array[] = $arr[$i]; } } //再分別對左邊和右邊的數組進行相同的排序處理方式//遞歸調用這個函數,並記錄結果$left_array = quick_sort($left_array); $right_array = quick_sort($right_array); //合併左邊標尺右邊return array_merge($left_array, array($base_num), $right_array); } $newArray=quick_sort($array); var_dump($newArray);?>5.希爾排序
原理：先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行依次直接插入排序。 。
時間複雜度:平均情況：O(n√n) 最好情況：O（nlog2n） 最壞情況：O（n2）
空間複雜度： O（1）
穩定性：不穩定
//JavaScript 希爾排序var array = [23,0,32,45,56,75,43,0,34]; var shellSort = function (arr) { var length=arr.length; var h=1; while(h<length/3) { h=3*h+1;//設置間隔} while(h>=1) { for(var i=h; i<length; i++) { for(var j=i; j>=h && arr[j]<arr[jh]; j-=h) { var temp =arr[jh]; arr[jh]=arr[j]; arr[j]=temp; } } h=(h-1)/3; } return arr; } var newArray = shellSort(array); console.log(newArray); <?php//希爾排序$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;//設置間隔} while($h>=1) { for($i=$h; $i<$length; $i++) { for($j=$i; $j>=$h && $arr[$j]<$arr[$j-$h]; $j-=$h) { $temp =$arr[$j-$h]; $arr[$j-$h]=$arr[$j]; $arr[$j]=$temp; } } $h=($h-1)/3; } return $arr; } $newArray = shellSort($array); var_dump($newArray)?>6.歸併排序
原理：假設初始序列含有n個記錄,則可以看成n個有序的子序列,每個子序列的長度為1,然後兩兩歸併,得到(不小於n/2的最小整數)個長度為2或1的有序子序列,再兩兩歸併,...如此重複,直至得到一個長度為n的有序序列為止
時間複雜度:平均情況：O(nlog2n) 最好情況：O（nlog2n） 最壞情況：O（nlog2n）
空間複雜度： O（1）
穩定性：穩定
//JavaScript 歸併排序function isArray1(arr){ if(Object.prototype.toString.call(arr) =='[object Array]'){ return true; }else{ return false; } } function merge(left,right){ var result=[]; if(!isArray1(left)){ left = [left]; } if(!isArray1(right)){ right = [right]; } while(left.length > 0&& right.length >0){ if(left[0]<right[0]){ result.push(left.shift()); }else{ result.push(right.shift()); } } return result.concat(left).concat(right); } function mergeSort(arr){ var len=arr.length; var lim ,work=[]; var i,j,k; if(len ==1){ return arr; } for(i=0;i<len;i++){ work.push(arr[i]); } work.push([]); for(lim=len;lim>1;){//lim為分組長度for(j=0,k=0;k<lim;j++,k=k+2){ work[j]=merge(work[k],work[k+1]); } work[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 //歸併排序function mergeSort(&$arr) { $len = count($arr);//求得數組長度mSort($arr, 0, $len-1); } //實際實現歸併排序的程序function mSort(&$arr, $left, $right) { if($left < $right) { //說明子序列內存在多餘1個的元素，那麼需要拆分，分別排序，合併//計算拆分的位置，長度/2 去整$center = floor(($left+$right) / 2); //遞歸調用對左邊進行再次排序： mSort($arr, $left, $center); //遞歸調用對右邊進行再次排序mSort($arr, $center+1, $right); //合併排序結果mergeArray($arr, $left, $center, $right); } } //將兩個有序數組合併成一個有序數組function mergeArray(&$arr, $left, $center, $right) { //設置兩個起始位置標記$a_i = $left; $b_i = $center+1; while($a_i<=$center && $b_i<=$right) { //當數組A和數組B都沒有越界時if($arr[$a_i] < $arr[$b_i]) { $temp[] = $arr[$a_i++]; } else { $temp[] = $arr[$b_i++]; } } //判斷數組A內的元素是否都用完了，沒有的話將其全部插入到C數組內： while($a_i <= $center) { $temp[] = $arr[$a_i++]; } //判斷數組B內的元素是否都用完了，沒有的話將其全部插入到C數組內： while($b_i <= $right) { $temp[] = $arr[$b_i++]; } //將$arrC內排序好的部分，寫入到$arr內： for($i=0, $len=count($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.堆排序
原理：堆排序就是利用堆進行排序的方法.基本思想是:將待排序的序列構造成一個大頂堆.此時,整個序列的最大值就是堆頂的根結點.將它移走(其實就是將其與堆數組的末尾元素交換, 此時末尾元素就是最大值),然後將剩餘的n-1個序列重新構造成一個堆,這樣就會得到n個元素的次大值.如此反复執行,便能得到一個有序序列了
時間複雜度：平均情況：O(nlog2n) 最好情況：O（nlog2n） 最壞情況：O（nlog2n）
空間複雜度： O（1）
穩定性：不穩定
//JavaScript 堆排序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); //將數組array構建成一個大頂堆} for (i = array.length - 1; i >= 0; i--) { /*把根節點交換出去*/ var temp = array[i]; array[i] = array[0]; array[0] = temp; /*餘下的數組繼續構建成大頂堆*/ heapAdjust(array, 0, i - 1); } return array; } function heapAdjust(array, start, max) { var temp = array[start];//temp是根節點的值for (var j = 2 * start; j < max; j *= 2) { if (j < max && array[j] < array[j + 1]) { //取得較大孩子的下標++j; } if (temp >= array[j]) break; array[start] = array[j]; start = j; } array[start] = temp; } var newArray = heapSort(array); console.log(newArray); <?php //堆排序function heapSort(&$arr) { #初始化大頂堆initHeap($arr, 0, count($arr) - 1); #開始交換首尾節點,並每次減少一個末尾節點再調整堆,直到剩下一個元素for($end = count($arr) - 1; $end > 0; $end--) { $temp = $arr[0]; $arr[0] = $arr[$end]; $arr[$end] = $temp; ajustNodes($arr, 0, $end - 1); } } #初始化最大堆,從最後一個非葉子節點開始,最後一個非葉子節點編號為數組長度/2 向下取整function initHeap(&$arr) { $len = count($arr); for($start = floor($len / 2) - 1; $start >= 0; $start--) { ajustNodes($arr, $start, $len - 1); } } #調整節點#@param $arr 待調整數組#@param $start 調整的父節點坐標#@param $end 待調整數組結束節點坐標function ajustNodes(&$arr, $start, $end) { $maxInx = $start; $len = $end + 1; #待調整部分長度$leftChildInx = ($start + 1) * 2 - 1; #左孩子坐標$rightChildInx = ($start + 1) * 2; #右孩子坐標#如果待調整部分有左孩子if($leftChildInx + 1 <= $len) { #獲取最小節點坐標if($arr[$maxInx] < $arr[$leftChildInx]) { $maxInx = $leftChildInx; } #如果待調整部分有右子節點if($rightChildInx + 1 <= $len) { if($arr[$maxInx] < $arr[$rightChildInx]) { $maxInx = $rightChildInx; } } } #交換父節點和最大節點if($start != $maxInx) { $temp = $arr[$start]; $arr[$start] = $arr[$maxInx]; $arr[$maxInx] = $temp; #如果交換後的子節點還有子節點,繼續調整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.基數排序
原理：將整數按位數切割成不同的數字，然後按每個位數分別比較。由於整數也可以表達字符串（比如名字或日期）和特定格式的浮點數，所以基數排序也不是只能使用於整數。
時間複雜度：平均情況：O(d(r+n)) 最好情況：O（d(n+rd)） 最壞情況：O（d(r+n)） r:關鍵字的基數d:長度n:關鍵字個數
空間複雜度： O（rd+n）
穩定性：穩定
<?php #基數排序,此處僅對正整數進行排序，至於負數和浮點數，需要用到補碼，各位有興趣自行研究#計數排序#@param $arr 待排序數組#@param $digit_num 根據第幾位數進行排序function counting_sort(&$arr, $digit_num = false) { if ($digit_num !== false) { #如果參數$digit_num不為空，則根據元素的第$digit_num位數進行排序for ($i = 0; $i < count($arr); $i++) { $arr_temp[$i] = get_specific_digit($arr[$i], $digit_num); } } else { $arr_temp = $arr; } $max = max($arr); $time_arr = array(); #儲存元素出現次數的數組#初始化出現次數數組for ($i = 0; $i <= $max; $i++) { $time_arr[$i] = 0; } #統計每個元素出現次數for ($i = 0; $i < count($arr_temp); $i++) { $time_arr[$arr_temp[$i]]++; } #統計每個元素比其小或相等的元素出現次數for ($i = 0; $i < count($time_arr) - 1; $i++) { $time_arr[$i + 1] += $time_arr[$i]; } #利用出現次數對數組進行排序for($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); #忽略這次對key排序的效率損耗} #計算某個數的位數function get_digit($number) { $i = 1; while ($number >= pow(10, $i)) { $i++; } return $i; } #獲取某個數字的從個位算起的第i位數function get_specific_digit($num, $i) { if ($num < pow(10, $i - 1)) { return 0; } return floor($num % pow(10, $i) / pow(10, $i - 1)); } #基數排序,以計數排序作為子排序過程function radix_sort(&$arr) { #先求出數組中最大的位數$max = max($arr); $max_digit = get_digit($max); for ($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);?>以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持武林網。