排序算法
冒泡排序
/** * 冒泡排序 * * @params $arr 要排序的数组 * @params $sot 默认升序排序,false 降序排序 */ function bubble_sort($arr,$sot = true) { $len = count($arr); for($i=0;$i<$len-1;$i++){ //用来判断是否发生交换,没有则可以结束排序 $flag = false; $mid = null; for($j=0;$j<$len-$i-1;$j++){ if($sot){ //升序排序 if($arr[$j]>$arr[$j+1]){ $mid = $arr[$j]; $arr[$j] = $arr[$j+1]; $arr[$j+1] = $mid; $flag = true; } }else{ //降序排序 if($arr[$j]<$arr[$j+1]){ $mid = $arr[$j]; $arr[$j] = $arr[$j+1]; $arr[$j+1] = $mid; $flag = true; } } } if(!$flag){ //排序已完成 break; } } return $arr; }
插入排序
/** * 插入排序 * * @params $arr 要排序的数组 * @params $flag 默认升序排序 false时,降序排序 */ function insertSort($arr,$flag = true) { $len = count($arr); for($i = 0;$i<$len-1;$i++){ $preIndex = $i; //记录位置 $current = $arr[$preIndex+1];//记录下一个的值 while($preIndex >=0){ if($flag){ if(($current > $arr[$preIndex])){ break; } }else{ if($current < $arr[$preIndex]){ break; } } $arr[$preIndex+1] = $arr[$preIndex]; $preIndex--; } $arr[$preIndex+1] = $current; } return $arr; }
选择排序
/** * 选择排序 * * @params $arr 要排序的数组 * @params $flag 默认true时,升序排序,否则降序排序 */ function select_sort($arr,$flag = true) { $len = count($arr); for($i=0;$i<$len;$i++){ $currentIndex = null; $currentIndex = $i; //当前比较元素的位置 for($j=$i+1;$j<$len;$j++){ if($flag ? $arr[$j]<$arr[$currentIndex] : $arr[$j]>$arr[$currentIndex]){ $currentIndex = $j; } } //交换元素 $mid = null; if($i != $currentIndex){ $mid = $arr[$i]; $arr[$i] = $arr[$currentIndex]; $arr[$currentIndex] = $mid; } } return $arr; }
希尔排序
/** * 希尔排序 * @params $arr 排序数组 * @params $flag 默认升序排序 false 则降序排序 */ function shell_sort($arr,$flag = true) { $len = count($arr); for($gap = floor($len/2);$gap > 0;$gap = floor($gap/2)){ for($j = $gap;$j < $len;$j++){ for($k = $j-$gap;$k >=0 && ($flag ? $arr[$k+$gap] < $arr[$k] : $arr[$k+$gap] > $arr[$k]);$k -= $gap){ $temp = $arr[$k]; $arr[$k] = $arr[$k+$gap]; $arr[$k+$gap] = $temp; } } } return $arr; }
二路归并排序
$arr = [10, 2, 4, 56, 29, 33, 293, 83, 2, 22]; function mergeSort(&$arr) { $left = 0; //第一个元素的下标 $right = count($arr) -1; //最后一个元素的下标 divSort($arr,$left,$right); } function divSort(&$arr,$left,$right) { if($left < $right) { //找出中间索引 $mid = floor(($left + $right) / 2); //分成两组 //对左边数组进行递归分组 divSort($arr,$left,$mid); //对右边数组进行递归分组 divSort($arr,$mid+1,$right); //将左右排好顺序的数组进行合并排序 merge($arr,$left,$mid,$right); } //将两个有序数组合并成一个有序数组 function merge(&$arr,$left,$mid,$right) { $i = $left; $j = $mid + 1; $temp = []; //临时合并数组 while($i <= $mid && $j <= $right) { if($arr[$i] < $arr[$j]){ $temp[] = $arr[$i]; $i++; }else{ $temp[] = $arr[$j]; $j++; } } //比完之后,假如左数组仍有剩余,则全部复制到 temp 数组 while($i <= $mid) { $temp[] = $arr[$i]; $i++; } //比完之后,假如右数组仍有剩余,则全部复制到 temp 数组 while($j <= $right) { $temp[] = $arr[$j]; $j++; } //将合并序列复制到原始序列中 for($k = 0; $k < count($temp); $k++) { $arr[$left + $k] = $temp[$k]; } } //测试 mergeSort($arr); var_dump($arr);
快速排序
function quickSort($arr) { $len = count($arr); if($len < 2) { return $arr; } $pivot = $arr[0]; //基准值 $leftArray = $rightArray = array(); for($i = 1; $i < $len; $i++) { if($arr[$i] < $pivot) { $leftArray[] = $arr[$i]; }else{ $rightArray[] = $arr[$i]; } } $leftArray = quickSort($leftArray); $rightArray = quickSort($rightArray); return array_merge($leftArray,array($pivot),$rightArray); } //测试 $newArr = quickSort($arr); var_dump($newArr);
计数排序
function countingSort($arr, $maxValue = null) { if ($maxValue === null) { $maxValue = max($arr); } for ($m = 0; $m < $maxValue + 1; $m++) { $bucket[] = null; } $arrLen = count($arr); for ($i = 0; $i < $arrLen; $i++) { if (!array_key_exists($arr[$i], $bucket)) { $bucket[$arr[$i]] = 0; } $bucket[$arr[$i]]++; } $sortedIndex = 0; foreach ($bucket as $key => $len) { if ($len !== null){ while($len > 0){ $arr[$sortedIndex++] = $key; $len--; } } } return $arr; } //测试 $newArr = countingSort($arr); var_dump($newArr);
本作品采用《CC 协议》,转载必须注明作者和本文链接