选择排序phpPHP排序算法计数选择插入合并快速冒泡希尔堆

//冒泡排序算法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.归并排序算法

选择排序phpPHP排序算法计数选择插入合并快速冒泡希尔堆 PHP

//归并排序算法（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 );

测试结果

---------正在天生 10000个无序数...天生 10000个无序数完成快速排序：正序耗时：0.098215103149414秒逆序耗时：0.10160207748413秒---------希尔排序：正序耗时：0.086393117904663秒逆序耗时：0.090419054031372秒---------计数排序：正序耗时：0.012665033340454秒逆序耗时：0.014392137527466秒---------插入排序：正序耗时：20.502465963364秒逆序耗时：21.812999010086秒---------堆排序：正序耗时：0.37758088111877秒逆序耗时：0.37416315078735秒---------归并排序：正序耗时：31.614189863205秒逆序耗时：22.086561918259秒---------选择排序：正序耗时：31.307014942169秒逆序耗时：31.074548959732秒---------冒泡排序：正序耗时：53.948215961456秒逆序耗时：57.123917102814秒

以下是测试代码

//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;}/