PHP排序算法实现：冒泡排序、选择排序、插入排序、归并排序、快速排序、希尔排序、堆排序、计数排序

比眉伴天荒 2022-10-25 04:51 201阅读 0赞

--------------------

PHP语言实现各排序算法：冒泡排序、选择排序、插入排序、归并排序、快速排序、希尔排序、堆排序、计数排序（原创内容，禁止转载）

--------------------

### 1.冒泡排序算法 ###

//冒泡 选择 插入 归并 快速 希尔 堆 计数

//冒泡排序算法php
 //author:Hengda
 //$arr 待排序数组
 //$mode false 正序，true倒序
 function bubbleSort( &$arr, $mode ){ 
 //数组元素数
 $len = count( $arr );
 //生成阶梯
 for( $i = 0; $i < $len - 1; $i++ ){ 
 //遍历当前阶梯
 for( $j = 0; $j < $len - $i - 1; $j++ ){ 
 //两两向后比较
 if( $mode ? $arr[ $j ] < $arr[ $j + 1 ] : $arr[ $j ] > $arr[ $j + 1 ] ){ 
 //交换相邻两个值
 $temp = $arr[ $j ];
 $arr[ $j ] = $arr[ $j + 1 ];
 $arr[ $j + 1 ] = $temp;
 }
 }
 }
 }

### 2.选择排序算法 ###

//选择排序算法（php）
 //author:Hengda
 //$arr 待排序数组
 //$mode false 正序，true倒序
 function selectionSort( &$arr, $mode ){ 
 //数组元素数
 $len = count( $arr );
 
 for( $i = 0; $i < $len - 1; $i++ ){ 
 $k = $i;//初始化最大或者最小值标记
 
 for( $j = $i + 1; $j < $len; $j++ ){ 
 //arr[$i] 与后面所有元素比较，并将最大或者最小元素做标记
 if( $mode ? $arr[ $j ] > $arr[ $k ] : $arr[ $j ] < $arr[ $k ] ){ 
 $k = $j;
 }
 }
 //遍历完交换 arr[i] 和 后续发现的最大或者最小值
 $temp = $arr[ $i ];
 $arr[ $i ] = $arr[ $k ];
 $arr[ $k ] = $temp;
 }
 
 //return $arr;
 }

### 3.插入排序算法 ###

//插入排序算法（php）
 //author:Hengda
 //$arr 待排序数组
 //$mode false 正序，true倒序
 function insertionSort( &$arr, $mode ){ 
 //数组元素数
 $len = count( $arr );
 //依次向后遍历每个元素，然后依次将此元素与后续元素作对比，比其大或者小的值向后移动，最后将当前元素填入空缺中
 for( $i = 1; $i < $len; $i++ ){ 
 $temp = $arr[ $i ];
 //依次向前比较并向后移动比其大或者小的
 for( $j = $i-1; $j >=0 && ( $mode ? $arr[ $j ] < $temp : $arr[ $j ] > $temp ); $j-- ){ 
 //向后移动
 $arr[ $j + 1 ] = $arr[ $j ];
 }
 //填充空缺
 $arr[ $j + 1 ] = $temp;
 }
 //return $arr;
 }

### 4.归并排序算法 ###

//归并排序算法（php）
 //author:Hengda
 //$arr 待排序数组
 //$start $len 每段待排序数据的起始位置和长度
 //$mode false 正序，true倒序
 function mergeSort( &$arr, $start, $len, $mode ){ 
 
 //左右分开排序
 if( $len > 4 ){ 
 
 $lstart = $start;//左侧部分起始位置
 $llen = floor( $len / 2 );//左侧部分长度
 $rstart = $lstart + $llen;//右侧部分起始位置
 $rlen = $len - $llen;//右侧部分长度
 
 mergeSort( $arr, 0, $lstart, $llen, $mode );
 mergeSort( $arr, 0, $rstart, $rlen, $mode );
 }
 
 //依次向后遍历每个元素，然后依次将此元素与后续元素作对比，比其大或者小的值向后移动，最后将当前元素填入空缺中
 for( $i = $start + 1; $i < $start + $len; $i++ ){ 
 
 $temp = $arr[ $i ];
 //依次向前比较并向后移动比其大或者小的
 for( $j = $i-1; $j >=$start && ( $mode ? $arr[ $j ] < $temp : $arr[ $j ] > $temp ); $j-- ){ 
 //向后移动
 $arr[ $j + 1 ] = $arr[ $j ];
 }
 //填充空缺
 $arr[ $j + 1 ] = $temp;
 }
 //return $arr;
 }

### 5.快速排序算法 ###

//快速排序算法（php）
 //author:Hengda
 //$arr 待排序数组
 //$start $end 每段待排序数据的起始位置（含）和终止位置（含）
 //$mode false 正序，true倒序
 function quickSort( &$arr, $start, $end, $mode ){ 
 
 if( $end > $start ){ 
 
 //初始化基准值
 $baseValue = $arr[ $end ];
 $j = $start;
 
 //遍历整段数据元素，小于等于基准值的放在基准准直左侧（正序），大于等于基准值的放在基准值左侧（倒序）
 for( $i = $start; $i <= $end; $i ++ ){ 
 
 //与基准值作比较
 if( $mode ? $arr[ $i ] >= $baseValue : $arr[ $i ] <= $baseValue ){ 
 
 //从左端开始依次排列放置，当前排列位置为$j，把原位置的元素向后交换
 $temp = $arr[ $j ];
 $arr[ $j ] = $arr[ $i ];
 $arr[ $i ] = $temp;
 //更新下一个应排列的位置
 $j++;
 }
 }
 //循环中$j在最后的++操作并未使用，这里需要减去，使$j正确标记左右分界元素
 $j--;
 
 //分界元素在两端是，则靠近分界元素的一端无需再排序
 //分界元素也无需再参与排序，因为左侧的一定小于等于分界元素，右侧的也一定大于等于分界元素
 //分别对分界元素左右两侧的数据段继续排序
 if( $j > $start ) quickSort( $arr, $start, $j-1, $mode );
 if( $j < $end ) quickSort( $arr, $j+1, $end, $mode );
 }
 
 //return $arr;
 }

### 6.希尔排序算法 ###

//希尔排序算法（php）
 //author: Hengda
 //$arr 待排序数组
 //$mode 排序模式，true 从大到小，false从小到大
 function shellSort( &$arr, $mode ){ 
 //$i,$j,$k循环控制变量,$temp 用于变量值交换，$gap不同分组间隙差，$len数组长度
 $i; $j; $temp; $gap = 1; $len = count( $arr );
 //计算
 while( $gap < floor( $len / 5 ) ){ 
 $gap = $gap * 5 + 1;
 }
 
 //遍历不同分组方案，并对每个分组方案进行排序
 for( $gap; $gap > 0; $gap = floor( $gap / 5 ) ){ 
 
 //以下为插入排序逻辑
 for( $i = $gap; $i < $len; $i++ ){ 
 
 $temp = $arr[ $i ];
 for( $j = $i - $gap; $j >= 0 && ( $mode ? $arr[ $j ] < $temp : $arr[ $j ] > $temp ); $j -= $gap ){ 
 $arr[ $j + $gap ] = $arr[ $j ];
 }
 $arr[ $j + $gap ] = $temp;
 
 } 
 }
 
 //return $arr;
 }

### 7.堆排序算法 ###

//堆排，堆节点下沉操作
 //author: Hengda
 //$arr 堆数组, $nodeNo 当前被操作节点序号, $heapLen 堆长度, $mode 排序模式，true 从大到小，false从小到大
 function heapNodeSink( &$arr, $nodeNo, $heapLen ,$mode ){ 
 
 $temp;//用于交换
 $minOrMaxNodeNo;//用于标记最大或最小节点的下标
 
 $leftChildNo = $nodeNo * 2 + 1;
 $rightChildNo = $leftChildNo + 1;
 
 $minOrMaxNodeNo = $nodeNo;//标记最大或者最小节点
 
 //如果有左孩子，则与左孩子比较，更新最大或者最小节点标记
 if( $leftChildNo < $heapLen ){ 
 if( $mode ? $arr[ $leftChildNo ] < $arr[ $minOrMaxNodeNo ] : $arr[ $leftChildNo ] > $arr[ $minOrMaxNodeNo ] ){ 
 $minOrMaxNodeNo = $leftChildNo;
 }
 }
 //如果有右孩子，则与右孩子比较，更新最大或者最小节点标记
 if( $rightChildNo < $heapLen ){ 
 if( $mode ? $arr[ $rightChildNo ] < $arr[ $minOrMaxNodeNo ] : $arr[ $rightChildNo ] > $arr[ $minOrMaxNodeNo ] ){ 
 $minOrMaxNodeNo = $rightChildNo;
 }
 }
 //如果需要交换，则交换之
 if( $minOrMaxNodeNo != $nodeNo ){ 
 //交换
 $temp = $arr[ $nodeNo ];
 $arr[ $nodeNo ] = $arr[ $minOrMaxNodeNo ];
 $arr[ $minOrMaxNodeNo ] = $temp;
 
 heapNodeSink( $arr, $minOrMaxNodeNo, $heapLen ,$mode );
 }
 //return $arr;
 }
 
 //堆排序算法（php）
 //author： Hengda
 //$arr 堆数组, $mode 排序模式，true 从大到小，false从小到大
 function heapSort( &$arr, $mode ){ 
 
 $i; $j; $len = count( $arr );
 //将无序数组规范为有序堆，即父总大于子，或者父总小于子
 //最后一个父节点
 $lastFatherNo = floor( $len / 2 ) - 1;
 //从最后一个父节点到第一个父节点，逐一做下沉操作
 for( $i = $lastFatherNo; $i >= 0; $i-- ){ 
 //下沉节点
 heapNodeSink( $arr, $i, $len ,$mode );
 }
 
 //将堆顶节点与 堆尾节点做交换，然后将堆长度减去1
 for( $i = $len - 1; $i > 0; $i-- ){ 
 //交换堆顶与堆尾
 $temp = $arr[ 0 ];
 $arr[ 0 ] = $arr[ $i ];
 $arr[ $i ] = $temp;
 //堆顶下沉操作
 heapNodeSink( $arr, 0, $i ,$mode );
 }
 //return $arr;
 }

### 8.计数排序算法 ###

//计数排序算法（php）由于php数组的键无序，所以统计需要ksort根据数组的键排序，所以做统计排序无意义，这几仅做实现。
 //author： Hengda
 //$arr 待排序数组,
 //$mode 排序模式，true 从大到小，false从小到大
 function countingSort( &$arr, $mode ){ 
 
 $len = count( $arr );
 
 $countArr = Array();
 //统计
 for( $i = 0; $i < $len; $i++ ){ 
 if( !isset( $countArr[ $arr[ $i ] ] ) ) $countArr[ $arr[ $i ] ] = 1;
 else $countArr[ $arr[ $i ] ]++;
 
 }
 
 $arr = Array();
 //根据键对统计数组排序
 $mode ? krsort( $countArr ) : ksort( $countArr );
 
 //
 foreach( $countArr as $k => $v ){ 
 for( $j = 0; $j < $v; $j++ ){ 
 $arr[] = $k;
 }
 }
 
 return $arr;
 }

### 9.测试以上各排序算法 ###

//测试排序10000个数
    $total = !empty( $_GET['total'] ) && is_numeric( $_GET['total'] ) ? $_GET['total'] : 10000;
    testSort( $total , true );

### 测试结果 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L29uZTMxMg_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L29uZTMxMg_size_16_color_FFFFFF_t_70 1]

### 以下是测试用代码 ###

//totalNum 测试排序的元素个数
 //isPrintArrData 是否打印数组数据
 function testSort( $totalNum, $isPrintArrData ){ 
 
 //生成测试数据
 $arr = makeData( $totalNum, $isPrintArrData );
 
 //1>调用测试函数，对 快速排序 算法进行测试
 testOneSortFunc( $arr, 'quickSort', ', 0, count( $arr ) - 1' , "快速排序", $isPrintArrData );
 
 //2>调用测试函数，对 希尔排序 算法进行测试
 //testOneSortFunc( $arr, 'shellSort', "", "希尔排序", $isPrintArrData );
 
 //3>调用测试函数，对 计数排序 算法进行测试
 testOneSortFunc( $arr, 'countingSort', "", "计数排序", $isPrintArrData );
 
 //4>调用测试函数，对 插入排序 算法进行测试
 testOneSortFunc( $arr, 'insertionSort', "", "插入排序", $isPrintArrData );
 
 //5>调用测试函数，对 堆排序 算法进行测试
 testOneSortFunc( $arr, 'heapSort', "", "堆排序", $isPrintArrData );
 
 //6>调用测试函数，对 归并排序 算法进行测试
 testOneSortFunc( $arr, 'mergeSort', ', 0, count( $arr ) ', "归并排序", $isPrintArrData );
 
 //7>调用测试函数，对 选择排序 算法进行测试
 testOneSortFunc( $arr, 'selectionSort', "", "选择排序", $isPrintArrData );
 
 //8>调用测试函数，对 冒泡排序 算法进行测试
 testOneSortFunc( $arr, 'bubbleSort', "", "冒泡排序", $isPrintArrData );
 
 }
 
 //
 function testOneSortFunc( $arr, $funcName, $funcOtherArgv, $textName, $isPrintArrData ){ 
 
 echo "--------- ";
 echo $textName."： ";
 
 //正序排序
 $arr1 = $arr;
 //$funcOtherArgv = ", 0, count(arr1) - 1";
 $stime = microtime( true );
 
 //quickSort( $arr1, 0, count( $arr ) - 1, false );
 eval( $funcName.'( $arr1'.$funcOtherArgv.", false );" );
 $etime = microtime( true );
 echo "正序耗时：".( $etime - $stime )."秒 ";
 if( $isPrintArrData ){ 
 echo "正序排序结果：";
 echo implode( ',', $arr1 )." ";
 }
 
 //逆序
 $arr2 = $arr;
 //$funcOtherArgv = ", 0, count(arr1) - 1";
 $stime = microtime( true );
 
 //quickSort( $arr2, 0, count( $arr ) - 1, true );
 eval( $funcName.'( $arr2'.$funcOtherArgv.", true );" );
 $etime = microtime( true );
 echo "逆序耗时：".( $etime - $stime )."秒 ";
 if( $isPrintArrData ){ 
 echo "倒序排序结果：";
 echo implode( ',', $arr2 )." ";
 }
 }
 
 //数据生成函数
 function makeData( $totalNum, $isPrintArrData ){ 
 
 echo "--------- ";
 echo "正在生成 " . $totalNum . "个无序数... ";
 
 $arr = Array();
 $i = $totalNum;
 while( $i-- ){ 
 $arr[] = mt_rand( 0, $totalNum );
 }
 
 echo "生成 " . $totalNum . "个无序数完成 ";
 if( $isPrintArrData ){ 
 echo "原始无序数据： ";
 echo implode( ",", $arr );
 }
 
 return $arr;
 }
 
 /* //生成$n个随机数组成的数组 //author:Hengda //$n随机数个数 function makeData( $n ){ $arr = Array(); $i = $n; while( $i-- ){ $arr[] = mt_rand( 0, $n ); } return $arr; } */

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L29uZTMxMg_size_16_color_FFFFFF_t_70]: /images/20221024/916fbdd97b3d4477b80bc63813cb4312.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L29uZTMxMg_size_16_color_FFFFFF_t_70 1]: /images/20221024/558bd0192b3e4f549abd73fff93f3f3b.png