PHP实现常见的排序算法


快速排序法(递归方式)

思路分析:

选择一个基准元素,通常选择第一个元素或者最后一个元素。通过一趟扫描,将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素。此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。本文来源:Seakee.top. 未经允许不得转载.

代码实现:

function quickSort($array)
{
    if (!is_array($array)) {
        return false;
    }

    $length = count($array);

    if ($length <= 1) {
        return $array;
    }

    $left = $right = [];

    for ($i = 1; $i < $length; $i++) {
        if ($array[$i] < $array[0]) {
            $left[] = $array[$i];
        } else {
            $right[] = $array[$i];
        }
    }

    $left  = quickSort($left);
    $right = quickSort($right);

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

$arr = [22, 13, 57, 76, 21, 19, 70, 34];

print_r(quickSort($arr));

冒泡排序

思路分析:

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

代码实现(非递归):

function bubbleSort($array)
{
    if (!is_array($array)) {
        return false;
    }

    $length = count($array);

    if ($length <= 1) {
        return $array;
    }

    for ($i = 1; $i < $length; $i++) {

        for ($j = 0; $j < $length - $i; $j++) {
            if ($array[$j] > $array[$j + 1]) {
                $temp          = $array[$j];
                $array[$j]     = $array[$j + 1];
                $array[$j + 1] = $temp;
            }
        }
    }

    return $array;
}

$arr = [7,78,24,45,37,2,1,67,423,75,32,16,53];

print_r(bubbleSort($arr));

代码实现(递归):

function recBubbleSort(array $array, int $length = 0)
{
    if (count($array) <= 1) {
        return $array;
    }

    if ($length <= 1) {
        return $array;
    } else {
        for ($i = 0; $i < $length - 1; $i++) {
            if ($array[$i] > $array[$i + 1]) {
                $temp          = $array[$i];
                $array[$i]     = $array[$i + 1];
                $array[$i + 1] = $temp;
            }
        }

        return  recBubbleSort($array, $length - 1);
    }
}

$arr = [10,9,8,7,6,5,4,3,2,1];

print_r(recBubbleSort($arr, 10));

选择排序

思路分析:

在要排序的一组数中,选出最小的一个数与第一个位置的数交换。然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一个数比较为止。本文来源:Seakee.top. 未经允许不得转载.

代码实现:

function selectSort(array $array)
{
    $length = count($array);

    if ($length <= 1) {
        return $array;
    }

    for ($i = 0; $i < $length - 1; $i++) {
        $p = $i;
        for ($j = $i + 1; $j < $length; $j++) {
            if ($array[$p] > $array[$j]) {
                $p = $j;
            }
        }

        if ($p != $i) {
            $temp      = $array[$i];
            $array[$i] = $array[$p];
            $array[$p] = $temp;
        }
    }

    return $array;
}

$arr = [1,3,7,8,4,6,22,55,33,53,73,2];

print_r(selectSort($arr));
未经允许禁止转载!!!!

1 对 “PHP实现常见的排序算法”的想法;

发表评论

电子邮件地址不会被公开。 必填项已用*标注