<?php $array = [23,0,32,45,56,75,43,0,34]; function quick_sort($arr) { //先判断是否需要继续进行 $length = count($arr); if($length <= 1) { return $arr; } $base_num = $arr[0];//选择一个标尺 选择第一个元素 //初始化两个数组 $left_array = array();//小于标尺的 $right_array = array();//大于标尺的 for($i=1; $i<$length; $i++) { //遍历 除了标尺外的所有元素，按照大小关系放入两个数组内 if($base_num > $arr[$i]) { //放入左边数组 $left_array[] = $arr[$i]; } else { //放入右边 $right_array[] = $arr[$i]; } } //再分别对 左边 和 右边的数组进行相同的排序处理方式 //递归调用这个函数,并记录结果 $left_array = quick_sort($left_array); $right_array = quick_sort($right_array); //合并左边 标尺 右边 return array_merge($left_array, array($base_num), $right_array); } $newArray=quick_sort($array); var_dump($newArray); ?>
5.希尔排序
原理：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。。
时间复杂度:平均情况：O(n√n) 最好情况：O（nlog2n） 最坏情况：O（n2）
空间复杂度：O（1）
稳定性：不稳定
//JavaScript 希尔排序 var array = [23,0,32,45,56,75,43,0,34]; var shellSort = function (arr) { var length=arr.length; var h=1; while(h<length/3) { h=3*h+1;//设置间隔 } while(h>=1) { for(var i=h; i<length; i++) { for(var j=i; j>=h && arr[j]<arr[j-h]; j-=h) { var temp =arr[j-h]; arr[j-h]=arr[j]; arr[j]=temp; } } h=(h-1)/3; } return arr; } var newArray = shellSort(array); console.log(newArray);
<?php //希尔排序 $array = [23,0,32,45,56,75,43,0,34]; function shellSort($arr) { $length=count($arr); $h=1; while($h<$length/3) { $h=3*$h+1;//设置间隔 } while($h>=1) { for($i=$h; $i<$length; $i++) { for($j=$i; $j>=$h && $arr[$j]<$arr[$j-$h]; $j-=$h) { $temp =$arr[$j-$h]; $arr[$j-$h]=$arr[$j]; $arr[$j]=$temp; } } $h=($h-1)/3; } return $arr; } $newArray = shellSort($array); var_dump($newArray) ?>
6.归并排序
原理：假设初始序列含有n个记录,则可以看成n个有序的子序列,每个子序列的长度为1,然后两两归并,得到(不小于n/2的最小整数)个长度为2或1的有序子序列,再两两归并,...如此重复,直至得到一个长度为n的有序序列为止
时间复杂度:平均情况：O(nlog2n) 最好情况：O（nlog2n） 最坏情况：O（nlog2n）
空间复杂度：O（1）
稳定性：稳定
//JavaScript 归并排序 function isArray1(arr){ if(Object.prototype.toString.call(arr) =='[object Array]'){ return true; }else{ return false; } } function merge(left,right){ var result=[]; if(!isArray1(left)){ left = [left]; } if(!isArray1(right)){ right = [right]; } while(left.length > 0&& right.length >0){ if(left[0]<right[0]){ result.push(left.shift()); }else{ result.push(right.shift()); } } return result.concat(left).concat(right); } function mergeSort(arr){ var len=arr.length; var lim ,work=[]; var i,j,k; if(len ==1){ return arr; } for(i=0;i<len;i++){ work.push(arr[i]); } work.push([]); for(lim=len;lim>1;){//lim为分组长度 for(j=0,k=0;k<lim;j++,k=k+2){ work[j]=merge(work[k],work[k+1]); } work[j]=[]; lim=Math.floor((lim+1)/2); } return work[0]; } var array = [23,0,32,45,56,75,43,0,34]; console.log(mergeSort(array));
<?php //归并排序 function mergeSort(&$arr) { $len = count($arr);//求得数组长度 mSort($arr, 0, $len-1); } //实际实现归并排序的程序 function mSort(&$arr, $left, $right) { if($left < $right) { //说明子序列内存在多余1个的元素，那么需要拆分，分别排序，合并 //计算拆分的位置，长度/2 去整 $center = floor(($left+$right) / 2); //递归调用对左边进行再次排序： mSort($arr, $left, $center); //递归调用对右边进行再次排序 mSort($arr, $center+1, $right); //合并排序结果 mergeArray($arr, $left, $center, $right); } } //将两个有序数组合并成一个有序数组 function mergeArray(&$arr, $left, $center, $right) { //设置两个起始位置标记 $a_i = $left; $b_i = $center+1; while($a_i<=$center && $b_i<=$right) { //当数组A和数组B都没有越界时 if($arr[$a_i] < $arr[$b_i]) { $temp[] = $arr[$a_i++]; } else { $temp[] = $arr[$b_i++]; } } //判断 数组A内的元素是否都用完了，没有的话将其全部插入到C数组内： while($a_i <= $center) { $temp[] = $arr[$a_i++]; } //判断 数组B内的元素是否都用完了，没有的话将其全部插入到C数组内： while($b_i <= $right) { $temp[] = $arr[$b_i++]; } //将$arrC内排序好的部分，写入到$arr内： for($i=0, $len=count($temp); $i<$len; $i++) { $arr[$left+$i] = $temp[$i]; } } $arr = array(23,0,32,45,56,75,43,0,34); mergeSort($arr); var_dump($arr); ?>