php - @amazeUI - 2016-11-22 13:39:50
要说起对数组进行排序，php很擅长，php有非常多的数组函数，其中就包括了排序。冒泡排序，选择排序，插入排序，今天将这三种排序思想及原理进行记录，及自己写的一个排序函数。
冒泡排序法，名字很有意思，也是我认为最好理解其思想及原理的一个排序法。
//冒泡(第一层循环只做循环次数限制，第二层循环两两相邻的比较，数值大的往下沉，数值小的往上浮)
public function bubbleSort($arr)
{
for ($i = 0; $i < count($arr) - 1; $i += 1) {
$temp = 0;//交换变量
$flag = true;//一个记录标志
for ($j = 0; $j < count($arr) - 1 - $i; $j += 1) {
if ($arr[$j] > $arr[$j + 1]) {
$temp = $arr[$j];
$arr[$j] = $arr[$j + 1];
$arr[$j + 1] = $temp;
$flag = false;
}
}
if ($flag === true) {
return '已为有序';
}
}
return $arr;
}
传进来一个数组，循环这个数组，第一层for循环判断-1是因为按照冒泡排序来讲，假设有5个键，有四个确认了位置的话第五个自然是在它该在的位置，所以无需多循环一遍。第二层For循环开始取相邻的比较，如果判断成立则利用temp变量互换位置，然后再挨个比较。假设传进去的数组是这样array(5,0,-1);在第一次排序后也就是第二层循环的第一次循环，$arr是(0,5,-1),第二次$arr(0,-1,5),第三次第二层已跳出，判断已经不成立，跳回第一层循环，继续开始第二层循环第二层循环只会执行一遍$arr(-1,0,5)执行完毕后返回已排好序的数组。flag有优化代码的作用，如果传进来的数组本身就是一个有序数组的话，是不会走第二层循环的if条件的，所以flag===true，第二层循环完成后就会直接返回不会再经过第一层循环了。冒泡排序利用第二层的相邻的两个键值做对比，完成互换位置，这是核心思想。这个冒泡应该是再没得优化了，网上那些优化顶多也就优化成这样。
//选择
public function selectSort($arr)//假设当前的值为最小的，如果找到比他还小的就互换位置
{
for ($i = 0; $i < count($arr); $i += 1) {
$minval = $arr[$i];
$minkey = $i;
$flag = true;
for ($j = $i + 1; $j < count($arr); $j += 1) {//循环过后最终最小值出现
if ($arr[$j] < $minval) {
$minval = $arr[$j];
$minkey = $j;
$flag = false;
}
}
if ($flag == false) {//说明最小值有经过交换到$i位
$arr[$minkey] = $arr[$i];
$arr[$i] = $minval;
}
}
return $arr;
}
选择排序法的思想，假设第一个键为最小值，从第二层循环开始轮番跟假设值进行比较比较成功后进行换为，第二层循环结束后，此数组中最小的值被交换到最前面，接着又开始第一层循环。这个选择排序法，我看很多网上还加了一个交换变量，其实这里没必要用到交换变量，因为假设值的键和值都已经做了存储了。选择排序法在跳出第二层循环的时候就会永久确认一个数值的位置，这点和冒泡不一样。其实选择排序法还有更加简洁的办法，我写的这个选择排序在网上能查到的应该算是简洁明了的了，但是其实这个选择排序法还能更加简洁！最后讲，这是第一次尝试写冒泡中，当时思维比较混乱的时候写出来的，思想其实跟选择排序是一样的，但是比这个选择排序要简洁得多，但是相对起理解选择排序法来说，还是这个更好去理解。
//插入排序--效率较高
public function insertSort($arr)//先默认键为0的值已经为有序，键值为$i的为待插入数，只要待插入数小于前面的数，就代表不确定插入位置，
//插入位置的确定是待插入数$i,$i要比$i-1要大比$i+1要小
{
for ($i = 1; $i < count($arr); $i += 1) {
$inserval = $arr[$i];//待插入数
$inserindex = $i - 1;//与前面一位数字进行比较
while ($inserindex >= 0 && $inserval < $arr[$inserindex]) {//只要键大于或等于0并且待插入数要小于前面一位数，
$arr[$inserindex + 1] = $arr[$inserindex];//如果小于的话，把比较数往后面挪一下
$inserindex -= 1;//此时将比较数再往前一步，相当于带插入数还不确定位置，还要跟前面的再次比较一下
}
//当以上条件不满足，即将走到这一步，
$arr[$inserindex + 1] = $inserval;//将待插入数插入(插入位置绝对是比较数字位置后一位)
}
return $arr;
}
插入排序，跟玩牌一样，确认一张牌不动，比不动牌小的往左放，大的往右边放。插入排序效率要相对于高一些。
下面要贴出来的是我巧合之中自己摸索出来的一个排序，核心思想其实还是跟选择排序一样，但是你多看几遍会发现其实完全没有必要将$arr[$i]的键值保存下来，因为在当前循环中$i并不会改变,只需要一个交换变量就够了。所以看下面。
public function mySort($arr)//在一轮中找到最小值
{
$temp = 0;
for ($i = 0; $i < count($arr) - 1; $i += 1) {
for ($j = 0 + $i; $j < count($arr); $j += 1) {
if ($arr[$i] > $arr[$j]) {
$temp = $arr[$i];
$arr[$i] = $arr[$j];
$arr[$j] = $temp;
}
}
}
return $arr;
}
这看起来是不是更加简洁明了？核心思想其实是跟选择排序一模一样哦。
网友评论