php 排序算法 ：冒泡、快速、选择、插入（搜集于网络）
2018-07-03 本文已影响69人
__o__o
冒泡排序
冒泡排序（Bubble Sorting）的基本思想是：
冒泡排序
代码：
/**
* 冒泡排序
*
* @param $arr, array 需要排序的数组
*
* @return array 排序好的数组
*/
function bubble_sort($arr) {
//利用双重循环完成
//外层循环控制 比较的轮数，每轮会将一个最大的气泡（数）浮到水面。
//如果数组的元素个数为N 则需要N-1轮完成
for($i=0, $len=count($arr); $i<$len-1; $i++) {
//内层循环控制 的比较的次数，
//第一轮需要比较 N-1次
//第二轮需要比较 N-2次
//比较次数由 $len-$i-1
for($j=0; $j<$len-$i-1; $j++) {
//比较相邻的两个元素，将大的元素放到后边
// 相邻的下标使用 $j 和 $j+1 标志
if($arr[$j] > $arr[$j+1]) {
//判断 前面的比后边的大，需要交换位置
$tmp = $arr[$j];
$arr[$j] = $arr[$j+1];
$arr[$j+1] = $tmp;
}
}
}
//返回比较后的数组
return $arr;
}
//测试
$arr1 = array(1, 3, 0, 2, 6, 2);
print_r(bubble_sort($arr1));
快速排序
快速排序（Quicksort）是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列.
快速排序
代码：
<?php
/**
*快速排序
*
* @param array $arr 需要排序的数组
*
* @return array 排序好的数组
*/
function quick_sort($arr) {
//先判断是否需要继续进行
$length = count($arr);
if($length <= 1) {
return $arr;
}
//如果没有返回，说明数组内的元素个数 多余1个，需要排序
//选择一个标尺
//选择第一个元素
$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);
}
//$arr = array(1, 5, 0, 4, 2, 1, 5, 4);
$arr = include 'arr.php';
print_r(quick_sort($arr));
选择排序
选择排序（select sorting）也是一种简单的排序方法。它的基本思想是：第一次从R[0]R[n-1]中选取最小值，与R[0]交换，第二次从R[1]R[n-1]中选取最小值，与R[1]交换，第三次从R[2]R[n-1]中选取最小值，与R[2]交换，…，第i次从R[i-1]R[n-1]中选取最小值，与R[i-1]交换，…, 第n-1次从R[n-2]~R[n-1]中选取最小值，与R[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。
选择排序
代码：
/**
* 选择排序
* 思路： 每次选择一个相应的元素，然后将其放到制定位置
*
* @param $arr array 待排序的数组
*
* @return array 排序好的数组
*/
function select_sort($arr) {
//实现思路
//双重循环完成，外层控制轮数，当前的最小值。
//内层 控制的比较次数
//$i 当前最小值的位置， 需要参与比较的元素
for($i=0, $len=count($arr); $i<$len-1; $i++) {
//先假设最小的值的位置
$p = $i;
//$j 当前都需要和哪些元素比较，$i 后边的
for($j=$i+1; $j<$len; $j++) {
//$arr[$p] 是 当前已知的最小值
if($arr[$p] > $arr[$j]) {
//比较，发现更小的,
//记录下最小值的位置
//并且在下次比较时， 应该采用已知的最小值进行比较。
$p = $j;
}
}
//已经确定了当前的最小值的位置，保存到$p中。
//如果发现 最小值的位置与当前假设的位置$i不同，则位置互换即可
if($p != $i) {
$tmp = $arr[$p];
$arr[$p] = $arr[$i];
$arr[$i] = $tmp;
}
}
//返回最终结果
return $arr;
}
$arr = array(4, 1, 2, 6, 5, 3);
print_r(select_sort($arr));
插入排序
插入排序（Insertion Sorting）的基本思想是：
插入排序
代码：
function insert_sort($arr) {
//区分 哪部分是已经排序好的
//哪部分是没有排序的
//找到其中一个需要排序的元素
//这个元素 就是从第二个元素开始，到最后一个元素都是这个需要排序的元素
//利用循环就可以标志出来
//i循环控制 每次需要插入的元素，一旦需要插入的元素控制好了，
//间接已经将数组分成了2部分，下标小于当前的（左边的），是排序好的序列
for($i=1, $len=count($arr); $i<$len; $i++) {
//获得当前需要比较的元素值。
$tmp = $arr[$i];
//内层循环控制 比较 并 插入
for($j=$i-1;$j>=0;$j--) {
// $arr[$i];//需要插入的元素
// $arr[$j];//需要比较的元素
if($tmp < $arr[$j]) {
//发现插入的元素要小，交换位置
//将后边的元素与前面的元素互换
$arr[$j+1] = $arr[$j];
//将前面的数设置为 当前需要交换的数
$arr[$j] = $tmp;
} else {
//如果碰到不需要移动的元素
//由于是已经排序好是数组，则前面的就不需要再次比较了。
break;
}
}
}
//将这个元素 插入到已经排序好的序列内。
//返回
return $arr;
}
$arr = array(3, 1, 5, 0, 7, 2);
print_r(insert_sort($arr));
