PHP实现常用排序算法的方法(2)

2 冒泡排序

冒泡排序是一种简单的排序算法。

算法重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。

走访数列的工作重复地进行，直到没有再需要交换，也就是说该数列已经排序完成。

因为排序过程让较大的数往下沉，较小的往上冒，故而叫冒泡法。

算法步骤：

从第一个元素开始，比较相邻的元素，如果第一个比第二个大，就交换他们两个。

从开始第一对到结尾的最后一对，对每一对相邻元素作同样的工作。比较结束后，最后的元素应该会是最大的数。

对所有的元素重复以上的步骤，除了最后一个。

重复上面的步骤，每次比较的对数会越来越少，直到没有任何一对数字需要比较。

PHP代码实现：

function bubbleSort($arr)
 {
 $len = count($arr);
 
 for($i = 1; $i < $len; $i++) {
 for($k = 0; $k < $len - $i; $k++) {
 if($arr[$k] > $arr[$k + 1]) {
 $tmp = $arr[$k + 1];
 $arr[$k + 1] = $arr[$k];
 $arr[$k] = $tmp;
 }
 }
 } 
 return $arr;
 }

3 插入排序

插入排序是一种简单直观的排序算法。

插入排序的工作原理是：将需要排序的数，与前面已经排好序的数据从后往前进行比较，使其插入到相应的位置。

插入排序在实现上，通常采用in-place排序，即只需用到O(1)的额外空间的排序。

因而，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

算法步骤：

从第一个元素开始，该元素可以认为已经被排序；

取出下一个元素，在已经排序的元素序列中从后向前扫描；

如果以排序的元素大于新元素，将该元素移到下一位置；

重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；

将新元素插入到该位置中；

重复步骤2。

PHP代码实现：

function insertSort($arr)
 {
 $len = count($arr); 
 
 for ($i = 1; $i < $len; $i++) {
 $tmp = $arr[$i];
 for ($j = $i - 1; $j >= 0; $j--) {
 if ($tmp < $arr[$j]) {
 $arr[$j + 1] = $arr[$j];
 $arr[$j] = $tmp;
 } else {
 break;
 }
 }
 }
 
 return $arr;
 }

4 选择排序

选择排序是一种简单直观的排序算法。