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