php语言实现的7种根本的排序方法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了php语言实现的7种根本的排序方法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含6016字，纯文字阅读大概需要9分钟。

内容图文

今天总结了一下常用的7种排序方法，并用php语言实现。

1. 直接插入排序

    1 /* 2  *    直接插入排序,插入排序的思想是：当前插入位置之前的元素有序， 3  *    若插入当前位置的元素比有序元素最后一个元素大，则什么也不做， 4  *    否则在有序序列中找到插入的位置，并插入 5  */ 6 function insertSort($arr) { 7     $len = count($arr);     8     for($i = 1; $i < $len; $i++) { 9         if($arr[$i-1] > $arr[i]) {10             for($j = $i - 1;$j >= 0; $j-- ) {11                 $tmp = $arr[$j+1];12                 if($tmp < $arr[$j]) {13                     $arr[$j+1] = $arr[$j];14                     $arr[$j] = $tmp;15                 }else{16                     break;17                 }                    18             }    19         }20     }    21     return $arr;22 }

2. 冒泡排序

    1 /* 2     冒泡排序,冒泡排序思想：进行 n-1 趟冒泡排序， 每趟两两比较调整最大值到数组（子数组）末尾 3 */ 4 function bubbleSort($arr) { 5     $len = count($arr); 6     for($i = 1; $i < $len; $i++) { 7         for($j = 0; $j < $len-$i; $j++) { 8             if($arr[$j] > $arr[$j+1]) { 9                 $tmp = $arr[$j+1];10                 $arr[$j+1] = $arr[$j];11                 $arr[$j] = $tmp;12             }13         }14     }15     return $arr;16 }    

3. 简单选择排序

    1 /* 2     简单选择排序, 简单排序思想：从数组第一个元素开始依次确定从小到大的元素 3 */ 4 function selectSort($arr) { 5     $len = count($arr); 6     for($i = 0; $i < $len; $i++) { 7         $k = $i; 8         for($j = $i+1; $j < $len; $j++) { 9             if($arr[$k] > $arr[$j]) {10                 $k = $j;11             }12         }13         if($k != $i) {14             $tmp = $arr[$i];15             $arr[$i] = $arr[$k];16             $arr[$k] = $tmp;17         }18     }19     return $arr;20 }

4. 希尔排序

    1 /* 2     希尔排序,希尔排序原理：将数组按指定步长分隔成若干子序列，然后分别对子序列进行排序（在这是直接） 3 */ 4 function shellSort($arr) { 5     $len = count($arr); 6     $k = floor($len/2); 7     while($k > 0) { 8         for($i = 0; $i < $k; $i++) { 9             for($j = $i; $j < $len, ($j + $k) < $len; $j = $j + $k) {10                 if($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     }19     return $arr;20 }

5. 快速排序

    1 /* 2  *    快速排序,快排思想：通过一趟排序将待排的记录分为两个独立的部分，其中一部分的记录的关键字均不大于 3  *    另一部分记录的关键字，然后再分别对这两部分记录继续进行快速排序，以达到整个序列有序，具体做法需要 4  *    每趟排序设置一个标准关键字和分别指向头一个记录的关键字和最后一个记录的关键字的指针。 5  *    quickSort($arr, 0, count($arr) -1); 6  */ 7 function quickSort(&$arr,$low,$high) { 8     if($low < $high) { 9         $i = $low;10         $j = $high;11         $primary = $arr[$low];12         while($i < $j) {13             while($i < $j && $arr[$j] >= $primary) {14                 $j--;15             }16             if($i < $j) {17                 $arr[$i++] = $arr[$j];18             }19             while($i < $j && $arr[$i] <= $primary) {20                 $i++;21             }22             if($i < $j) {23                 $arr[$j--] = $arr[$i];24             }25         }26         $arr[$i] = $primary;27         quickSort($arr, $low, $i-1);28         quickSort($arr, $i+1, $high);29     }30 }

6. 堆排序

    1 /* 2     堆排序 3 */ 4  5 // 调整子堆的为大根堆的过程，$s为子堆的根的位置，$m为堆最后一个元素位置 6 function heapAdjust(&$arr, $s, $m) { 7     $tmp = $arr[$s]; 8     // 在调整为大根堆的过程中可能会影响左子堆或右子堆 9     // for循环的作用是要保证子堆也是大根堆10     for($j = 2*$s + 1; $j <= $m; $j = 2*$j + 1) {11         // 找到根节点的左右孩子中的最大者，然后用这个最大者与根节点比较，12         // 若大则进行调整，否则符合大根堆的 特点跳出循环    13         if($j < $m && $arr[$j] < $arr[$j+1]) {14             $j++;15         }16         if($tmp >= $arr[$j] ) {17             break;18         }19         $arr[$s] = $arr[$j];20         $s = $j;21     }22     $arr[$s] = $tmp;23 }24 25 // 堆排序26 function heapSort($arr) {27     $len = count($arr);28     // 依次从子堆开始调整堆为大根堆29     for($i = floor($len/2-1); $i >= 0; $i--) {30         heapAdjust($arr, $i, $len-1);31     }32     // 依次把根节点调换至最后一个位置，再次调整堆为大根堆，找到次最大值，33     // 依次类推得到一个有序数组34     for($n = $len-1; $n > 0; $n--) {35         $tmp = $arr[$n];36         $arr[$n] = $arr[0];37         $arr[0] = $tmp;38         heapAdjust($arr, 0, $n-1);39     }40     return $arr;41 }

7. 归并排序

    1 /* 2     归并排序,这里实现的是两路归并 3 */ 4 // 分别将有序的$arr1[s..m]、$arr2[m+1..n]归并为有序的$arr2[s..n] 5 function Merge(&$arr1, &$arr2, $s, $m, $n) { 6     for($k = $s,$i = $s, $j = $m+1; $i <= $m && $j <= $n; $k++) { 7         if($arr1[$i]<$arr1[$j]) { 8             $arr2[$k] = $arr1[$i++]; 9         }else {10             $arr2[$k] = $arr1[$j++];11         }12     }13     if($i <= $m) {14         for(; $i <= $m; $i++) {15             $arr2[$k++] = $arr1[$i];16         }17     } else if($j <= $n) {18         for(; $j <= $n; $j++) {19             $arr2[$k++] = $arr1[$j];20         }21     }22 }23 24 // 递归形式的两路归并25 function MSort(&$arr1, &$arr2, $s, $t) {26     if($s == $t) {27         $arr2[$s] = $arr1[$s];28     }else {29         $m = floor(($s+$t)/2);30         $tmp_arr = array();31         MSort($arr1, $tmp_arr, $s, $m);32         MSort($arr1, $tmp_arr, $m+1, $t);33         Merge($tmp_arr, $arr2, $s, $m, $t);34     }35 }36 37 // 对一位数组$arr[0..n-1]中的元素进行两路归并38 function mergeSort($arr) {39     $len = count($arr);40     MSort($arr, $arr, 0, $len-1);41     return $arr;42 }

   使用经验

1. 若排序的记录数目n较小时，可以采用直接插入排序和简单选择排序，当记录本身信息量较大时，用简单选择排序方法较好。
2. 若待排序记录按关键字基本有序，适合采用直接插入排序和冒泡排序。
3. 若n值较大时，可以采用快速排序、堆排序和归并排序。另外快速排序被认为是内部排序方法中最好的方法。

内容总结

以上是互联网集市为您收集整理的php语言实现的7种根本的排序方法全部内容，希望文章能够帮你解决php语言实现的7种根本的排序方法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端