| 排序算法 | 平均時間復雜度 | | --- | --- | | 冒泡排序 | O(n2) | | 選擇排序 | O(n2) | | 插入排序 | O(n2) | | 希爾排序 | O(n1.5) | | 快速排序 | O(N\*logN) | | 歸并排序 | O(N\*logN) | | 堆排序 | O(N\*logN) | | 基數排序 | O(d(n+r)) | 1.冒泡排序(BubbleSort): * 基本思想: ``` 兩個數比較大小，較大的數下沉，較小的數冒起來。 ``` * 過程： ``` 比較相鄰的兩個數據，如果第二個數小，就交換位置。 從后向前兩兩比較，一直到比較最前兩個數據。最終最小數被交換到起始的位置，這樣第一個最小數的位置就 排好了。 繼續重復上述過程，依次將第2.3...n-1個最小數排好位置。 ``` * php代碼實現: ``` //冒泡排序 public static function bubbleSort($arr){ for($i=0;$i<count($arr)-1;$i++){ //表示趟數，一共arr.length-1次。 for($j=count($arr)-1;$j>$i;$j--){ if($arr[$j]<$arr[$j-1]){ //數據比較交換 $temp=$arr[$j]; $arr[$j]=$arr[$j-1]; $arr[$j-1]= $temp; } } } return $arr; } ``` 2.選擇排序(SelctionSort): * 基本思想: ``` 在長度為N的無序數組中，第一次遍歷n-1個數，找到最小的數值與第一個元素交換。 第二次遍歷n-2個數，找到最小的數值與第二個元素交換。 ...... 第n-1次遍歷，找到最小的數值與第n-1個元素交換，排序完成。 ``` * php代碼實現: ``` //選擇排序 public static function selctionSort($arr){ for($i=0;$i<count($arr)-1;$i++){ $minIndex = $i; for($j=$i+1;$j<count($arr);$j++){ if($arr[$j]<$arr[$minIndex]){ //查找最小的索引 $minIndex = $j; } } if($minIndex != $i){ //數組數據進行交換 $temp=$arr[$i]; $arr[$i]=$arr[$minIndex]; $arr[$minIndex]= $temp; } } return $arr; } ``` 3.插入排序(InsertSort): * 基本思想: ``` 在要排序的一組數中，假定前n-1個數已經排好序，現在將第n個數插到前面的有序數列中，使得這n個數也是排好順序的。如此反復循環，直到全部排好順序。 ``` * php代碼實現: ``` //插入排序 public static function insertSort($arr){ for($i=0;$i<count($arr)-1;$i++){ for($j=$i+1;$j>0;$j--){ if($arr[$j] < $arr[$j-1]){ //數據交換 $temp=$arr[$j-1]; $arr[$j-1]=$arr[$j]; $arr[$j]= $temp; }else{ //不需要交換 break; } } } return $arr; } ``` 4.希爾排序(ShellSort): * 基本思想: ``` 在要排序的一組數中，根據某一增量分為若干子序列，并對子序列分別進行插入排序。 然后逐漸將增量減小,并重復上述過程。直至增量為1,此時數據序列基本有序,最后進行插入排序。 ``` * php代碼實現: ``` //插入排序 public static function insertSort($arr){ for($i=0;$i<count($arr)-1;$i++){ for($j=$i+1;$j>0;$j--){ if($arr[$j] < $arr[$j-1]){ //數據交換 $temp=$arr[$j-1]; $arr[$j-1]=$arr[$j]; $arr[$j]= $temp; }else{ //不需要交換 break; } } } return $arr; } ```