PHP学习之排序

2017-06-26 本文已影响0人 Marnoon

排序分为内部排序和外部排序

内部排序：所有数据都加载到内存当中。主要方法有冒泡法、选择排序法、插入式排序法和快速排序法。

外部排序：数据量过大，无法全部加载到内存中，需要借助外部存储进行排序，将数据量分成多个文件，每个文件分别用内部排序法进行排序，排序后将文件合并。主要方法有合并排序法和直接合并排序法。

冒泡排序（升序排列）

思想：从第一个元素开始，对数组中两两相邻的元素比较，将值较小的元素放在前面，值较大的元素放在后面，一轮比较完毕，一个最大的数将成为数组中的最后一个元素。

冒泡排序示意图
```
$arr = array(1, 3, 6, 2, 4);
$temp = 0;
for ($i = 0; $i < count($arr)-1; $i++) { // 趟数
    for ($j = 0; $j < count($arr)-1-$i; $j++) {  // 比较次数
        if ($arr[$j] > $arr[$j+1]) {
            $temp = $arr[$j];
            $arr[$j] = $arr[$j+1];
            $arr[$j+1] = $temp;
        }
    }
}
print_r($arr);
// Array ( [0] => 1 [1] => 2 [2] => 3 [3] => 4 [4] => 6 )
```
Q1：趟数为什么是小于 $count($arr)-1 ，而不是小于 count($arr) ?
A1：因为 $i 表示趟数，同时又表示排序好的个数， $i 每加1，都表示已经排好了未排列里面的最大数。当 $i < count($arr) 时，最后一趟，只剩最后一个数，这个数根本不用比较。只剩一个坑，跳进里面就行了，用不着再一次比较。

Q2：比较次数为什么是 count($arr)-1-$i ?
A2：为什么是 count($arr)-1 ，因为 $j 表示的是比较次数，自己和自己不需要比较，只需要和自己后面的数比较就行了，所以是 count($arr)-1 ；那为什么还要减去 $i 呢？同样的道理， $i 同样表示已经排好了的个数，而且这些排好的都在最后面放着，也没有必要和排序好的再次比较。所以，最终结果就是 count($arr)-1-$i 。

选择排序法（升序排列）

思想：每一次从待排序的数据元素中选出最小的一个元素，存放在需要排列序列的起始位置，直到全部待排序的数据元素排完。

选择排序法示意图

$arr = array(1, 3, 6, 2, 4);
$temp = 0;
for ($i = 0; $i < count($arr)-1; $i++) {
    $minVal = $arr[$i];
    $minIndex = $i;
    for ($j = $i+1; $j < count($arr); $j++) {    // 找出最小数
        if ($minVal > $arr[$j]) {
            $minVal = $arr[$j];
            $minIndex = $j;
        }
    }
    // 交换
    $temp = $arr[$i];
    $arr[$i] = $arr[$minIndex];
    $arr[$minIndex] = $temp;
}
print_r($arr);
// Array ( [0] => 1 [1] => 2 [2] => 3 [3] => 4 [4] => 6 )

插入式排序法
插入式排序法又分为插入排序法、谢尔排序法 和 二叉树排序法。这里我们只举例基本的插入排序法

思想：分一个有序表（可以理解为数组）和一个无序表，开始时有序表中只包含一个元素，无序表中包含n-1个元素，排序过程每次从无序表中取出第一个元素，和有序表中的元素进行比较，插入到适当位置。

因为有序表和无序表刚好划分了一整个数组，所以在一个数组中就可以完成我们的排序。

$arr = array(1, 3, 6, 2, 4);
for ($i = 0; $i < count($arr); $i++) {
    $insertVal = $arr[$i+1];
  
    $sortIndex = $i-1;   // 从后往前比较
    while ($sortIndex >= 0 && $insertVal < $arr[$sortIndex]) {   // 判断位置是否合适；只要进入while循环，表示位置还不合适
        $arr[$sortIndex+1] = $arr[$sortIndex];   // 给要插入的数向后挪位置
        $sortIndex--;
    }
    
    // 插入数据(在比较的数的后面插入)
    $arr[$sortIndex+1] = $insertVal; 
}
print_r($arr);
// Array ( [0] => 1 [1] => 2 [2] => 3 [3] => 4 [4] => 6 )

快速排序法

思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据比另外一部分的数据都小，然后再按照此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

快速排序的速度非常快，不过在排序的瞬间，内存会暴涨。快速排序是用空间来换取时间的一种思想

快速排序法示意图

$arr = array(1, 3, 6, 2, 4);
function quickSort ($left, $right, &$array) {
    $l = $left;
    $r = $right;
    $pivot = $array[($left+$right)/2];   // 基准(这里取数组中间数，可以取数组中随便一个数)
    $temp = 0;
    while ($l < $r) {
        while ($array[$l] < $pivot) $l++;
        while ($array[$r] > $pivot) $r--;
      
        if ($l >= $r) break;
      
        $temp = $array[$l];
        $array[$l] = $array[$r];
        $array[$r] = $temp;
      
        if ($array[$l] == $pivot) --$r;
        if ($array[$r] == $pivot) ++$l;
    }
    
    if ($l == $r) {
        $l++;
        $r--;
    }
  
    if ($left < $r) quickSort($left, $r, $array);
    if ($right > $l) quickSort($l, $right, $array);
}
quickSort(0, count($arr)-1, $arr);
print_r($arr);
// Array ( [0] => 1 [1] => 2 [2] => 3 [3] => 4 [4] => 6 )

PHP学习之排序

猜你喜欢

热点阅读