| 排序算法 | 平均时间复杂度 | | --- | --- | | 冒泡排序 | 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; } ```