php语言实现的7种基本的排序方法
今天总结了一下常用的7种排序方法，并用php语言实现。
直接插入排序1/*2* 直接插入排序,插入排序的思想是：当前插入位置之前的元素有序，3* 若插入当前位置的元素比有序元素最后一个元素大，则什么也不做，4* 否则在有序序列中找到插入的位置，并插入5*/6functioninsertSort($arr) {7$len=count($arr);8for($i= 1;$i<$len;$i++) {9if($arr[$i-1] >$arr[i]) {10for($j=$i- 1;$j>= 0;$j--) {11$tmp=$arr[$j+1];12if($tmp<$arr[$j]) {13$arr[$j+1] =$arr[$j];14$arr[$j] =$tmp;15}else{16
break;17}18}19}20}21return$arr;22}
冒泡排序1/*2冒泡排序,冒泡排序思想：进行 n-1 趟冒泡排序， 每趟两两比较调整最大值到数组（子数组）末尾3*/4functionbubbleSort($arr) {5$len=count($arr);6for($i= 1;$i<$len;$i++) {7for($j= 0;$j<$len-$i;$j++) {8if($arr[$j] >$arr[$j+1]) {9$tmp=$arr[$j+1];10$arr[$j+1] =$arr[$j];11$arr[$j] =$tmp;12}13}14}15return$arr;16}
简单选择排序1/*2简单选择排序, 简单排序思想：从数组第一个元素开始依次确定从小到大的元素3*/4functionselectSort($arr) {5$len=count($arr);6for($i= 0;$i<$len;$i++) {7$k=$i;8for($j=$i+1;$j<$len;$j++) {9if($arr[$k] >$arr[$j]) {10$k=$j;11}12}13if($k!=$i) {14$tmp=$arr[$i];15$arr[$i] =$arr[$k];16$arr[$k] =$tmp;17}18}19return$arr;20}
希尔排序1/*2希尔排序,希尔排序原理：将数组按指定步长分隔成若干子序列，然后分别对子序列进行排序（在这是直接）3*/4functionshellSort($arr) {5$len=count($arr);6$k=floor($len/2);7while($k> 0) {8for($i= 0;$i<$k;$i++) {9for($j=$i;$j<$len, ($j+$k) <$len;$j=$j+$k) {10if($arr[$j] >$arr[$j+$k]) {11$tmp=$arr[$j+$k];12$arr[$j+$k] =$arr[$j];13$arr[$j] =$tmp;14}15}16}17$k=floor($k/2);18}19return$arr;20}
快速排序1/*2* 快速排序,快排思想：通过一趟排序将待排的记录分为两个独立的部分，其中一部分的记录的关键字均不大于3* 另一部分记录的关键字，然后再分别对这两部分记录继续进行快速排序，以达到整个序列有序，具体做法需要4* 每趟排序设置一个标准关键字和分别指向头一个记录的关键字和最后一个记录的关键字的指针。5* quickSort($arr, 0, count($arr) -1);6*/7functionquickSort(&$arr,$low,$high) {8if($low<$high) {9$i=$low;10$j=$high;11$PRimary=$arr[$low];12while($i<$j) {13while($i<$j&&$arr[$j] >=$primary) {14$j--;15}16if($i<$j) {17$arr[$i++] =$arr[$j];18}19while($i<$j&&$arr[$i] <=$primary) {20$i++;21}22if($i<$j) {23$arr[$j--] =$arr[$i];24}25}26$arr[$i] =$primary;27quickSort($arr,$low,$i-1);28quickSort($arr,$i+1,$high);29}30}
堆排序1/*2堆排序3*/45//调整子堆的为大根堆的过程，$s为子堆的根的位置，$m为堆最后一个元素位置6functionheapAdjust(&$arr,$s,$m) {7$tmp=$arr[$s];8//在调整为大根堆的过程中可能会影响左子堆或右子堆9// for循环的作用是要保证子堆也是大根堆10for($j= 2*$s+ 1;$j<=$m;$j= 2*$j+ 1) {11//找到根节点的左右孩子中的最大者，然后用这个最大者与根节点比较，12// 若大则进行调整，否则符合大根堆的 特点跳出循环13if($j<$m&&$arr[$j] <$arr[$j+1]) {14$j++;15}16if($tmp>=$arr[$j] ) {17
break;18}19$arr[$s] =$arr[$j];20$s=$j;21}22$arr[$s] =$tmp;23}2425//堆排序26functionheapSort($arr) {27$len=count($arr);28//依次从子堆开始调整堆为大根堆29for($i=floor($len/2-1);$i>= 0;$i--) {30heapAdjust($arr,$i,$len-1);31}32//依次把根节点调换至最后一个位置，再次调整堆为大根堆，找到次最大值，33// 依次类推得到一个有序数组34for($n=$len-1;$n> 0;$n--) {35$tmp=$arr[$n];36$arr[$n] =$arr[0];37$arr[0] =$tmp;38heapAdjust($arr, 0,$n-1);39}40return$arr;41}
归并排序1/*2归并排序,这里实现的是两路归并3*/4//分别将有序的$arr1[s..m]、$arr2[m+1..n]归并为有序的$arr2[s..n]5functionMerge(&$arr1, &$arr2,$s,$m,$n) {6for($k=$s,$i=$s,$j=$m+1;$i<=$m&&$j<=$n;$k++) {7if($arr1[$i]<$arr1[$j]) {8$arr2[$k] =$arr1[$i++];9}else{10$arr2[$k] =$arr1[$j++];11}12}13if($i<=$m) {14for(;$i<=$m;$i++) {15$arr2[$k++] =$arr1[$i];16}17}elseif($j<=$n) {18for(;$j<=$n;$j++) {19$arr2[$k++] =$arr1[$j];20}21}22}2324//递归形式的两路归并25functionMSort(&$arr1, &$arr2,$s,$t) {26if($s==$t) {27$arr2[$s] =$arr1[$s];28}else{29$m=floor(($s+$t)/2);30$tmp_arr=array();31MSort($arr1,$tmp_arr,$s,$m);32MSort($arr1,$tmp_arr,$m+1,$t);33Merge($tmp_arr,$arr2,$s,$m,$t);34}35}3637//对一位数组$arr[0..n-1]中的元素进行两路归并38functionmergeSort($arr) {39$len=count($arr);40MSort($arr,$arr, 0,$len-1);41return$arr;42}
使用经验若排序的记录数目n较小时，可以采用直接插入排序和简单选择排序，当记录本身信息量较大时，用简单选择排序方法较好。若待排序记录按关键字基本有序，适合采用直接插入排序和冒泡排序。若n值较大时，可以采用快速排序、堆排序和归并排序。另外快速排序被认为是内部排序方法中最好的方法。