首页 > 文章详情 > PHP 经典排序 冒泡排序/快速排序/选择排序

PHP 经典排序 冒泡排序/快速排序/选择排序

原创 YuanDong 2019-10-05 浏览量(41)

一、冒泡排序

思路分析:在要排序的一组数中,对当前还未排好的序列,从前往后对相邻的两个数依次进行比较和调整,让较大的数往下沉,较小的往上冒。即,每当两相邻的数比较后发现它们的排序与排序要求相反时,就将它们互换.
实现代码:

function bubbleSort(array $array) :array
{
    $length = count($array);
    if ($length > 1) {
        for ($i = 0; $i < $length; $i++) {
            for ($x = 0; $x < ($length - $i - 1); $x++) {
                if ($array[$x] > $array[$x + 1]) {
                    $tmp = $array[$x + 1];
                    $array[$x + 1] = $array[$x];
                    $array[$x] = $tmp;
                }
            }
        }
    }

    return $array;
}

运行分析: 准备数组 [9,3,8,13,26,7,6,1,33,2]

 初始排序
 9 - 3 - 8 - 13 - 26 - 7 - 6 - 1 - 33 - 2
 ---start
 3 - 8 - 9 - 13 - 7 - 6 - 1 - 26 - 2 - 33
 3 - 8 - 9 - 7 - 6 - 1 - 13 - 2 - 26 - 33
 3 - 8 - 7 - 6 - 1 - 9 - 2 - 13 - 26 - 33
 3 - 7 - 6 - 1 - 8 - 2 - 9 - 13 - 26 - 33
 3 - 6 - 1 - 7 - 2 - 8 - 9 - 13 - 26 - 33
 3 - 1 - 6 - 2 - 7 - 8 - 9 - 13 - 26 - 33
 1 - 3 - 2 - 6 - 7 - 8 - 9 - 13 - 26 - 33
 1 - 2 - 3 - 6 - 7 - 8 - 9 - 13 - 26 - 33
 1 - 2 - 3 - 6 - 7 - 8 - 9 - 13 - 26 - 33
 1 - 2 - 3 - 6 - 7 - 8 - 9 - 13 - 26 - 33

 ---end

二、快速排序

思路分析:找到当前数组中的任意一个元素(一般选择第一个元素),作为标准,新建两个空数组,遍历整个数组元素,如果遍历到的元素比当前的元素要小,那么就放到左边的数组,否则放到右面的数组,然后再对新数组进行同样的操作,不难发现,这里符合递归的原理,所以我们可以用递归来实现。
使用递归,则需要找到递归点和递归出口:

  • 递归点:如果数组的元素大于1,就需要再进行分解,所以我们的递归点就是新构造的数组元素个数大于1
  • 递归出口:我们什么时候不需要再对新数组不进行排序了呢?就是当数组元素个数变成1的时候,所以这就是我们的出口。

代码实现:

function quickSort(array $array) :array
{
    if ($array && is_array($array)) {
        $length = count($array);
        if ($length > 1) {
            $left = $right = [];
            for ($i = 1; $i < $length; $i ++) {
                // 判断当前元素的大小和第一个元素比较
                if ($array[$i] < $array[0]) {
                    $left[] = $array[$i];
                } else {
                    $right[] = $array[$i];
                }
            }

            // 递归调用
            if ($left) {
                $left = quickSort($left);
            }

            if ($right) {
                $right = quickSort($right);
            }

            return array_merge($left, [$array[0]], $right);
        }
    }

    return $array;
}

三、选择排序

思路分析:在要排序的一组数中,选出最小的一个数与第一个位置的数交换。然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一个数比较为止。

代码实现:

function selectSort(array $array) :array
{
    $length = count($array);
    if ($length > 1) {

        for ($i = 0; $i < $length - 1; $i ++) {
            $index = $i;
            for ($x = $i + 1; $x < $length; $x ++) {
                // 默认$array[$index] 为最小值
                if ($array[$index] > $array[$x]) {
                    // 记录最小值
                    $index = $x;
                }
            }

            // 已经确定最小值的位置,保持到$index中;如果发现最小值的位置与当前假设的位置$i不同,则位置互换即可。
            if ($index != $i) {
                $tmp = $array[$index];
                $array[$index] = $array[$i];
                $array[$i] = $tmp;
            }
        }
    }

    return $array;
}

运行分析: 准备数组 [9,3,8,13,26,7,6,1,33,2]

初始排序      9 - 3 - 8 - 13 - 26 - 7 - 6 - 1 - 33 - 2
第0轮排序结果 1 - 3 - 8 - 13 - 26 - 7 - 6 - 9 - 33 - 2 最小值1,交换值9
第1轮排序结果 1 - 2 - 8 - 13 - 26 - 7 - 6 - 9 - 33 - 3 最小值2,交换值3
第2轮排序结果 1 - 2 - 3 - 13 - 26 - 7 - 6 - 9 - 33 - 8 最小值3,交换值8
第3轮排序结果 1 - 2 - 3 - 6 - 26 - 7 - 13 - 9 - 33 - 8 最小值6,交换值13
第4轮排序结果 1 - 2 - 3 - 6 - 7 - 26 - 13 - 9 - 33 - 8 最小值7,交换值26
第5轮排序结果 1 - 2 - 3 - 6 - 7 - 8 - 13 - 9 - 33 - 26 最小值8,交换值26
第6轮排序结果 1 - 2 - 3 - 6 - 7 - 8 - 9 - 13 - 33 - 26 最小值9,交换值13
第7轮排序结果 1 - 2 - 3 - 6 - 7 - 8 - 9 - 13 - 33 - 26 最小值9,交换值13
第8轮排序结果 1 - 2 - 3 - 6 - 7 - 8 - 9 - 13 - 26 - 33 最小值26,交换值33

热门评论 (0)

网友评论 0 条评论 / 0 人参与