常见的四种排序算法

对下面的数据进行排序

$arr = [3, 5, 2, 4, 6];

冒泡排序

• 比较相邻的两个元素。如果第一个比第二个大，就交换他们两个
• 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
• 针对所有的元素重复以上的步骤，除了最后一个
• 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

优点：稳定

缺点：慢，每次只能移动相邻两个数据

实现：

function bubbleSort(array &$arr): void
{
    $num = count($arr);
    if ($num <= 1) {
        return;
    }
    for ($i = 0; $i < $num; $i++) {
        for ($j = 0; $j < $num - $i - 1; $j++) {
            if ($arr[$j] < $arr[$j + 1]) {
                $temp = $arr[$j];
                $arr[$j] = $arr[$j + 1];
                $arr[$j + 1] = $temp;
            }
        }
    }
}

/******************************/

print_r($arr);
bubbleSort($arr);
print_r($arr);

/*
输出：

Array
(
    [0] => 3
    [1] => 5
    [2] => 2
    [3] => 4
    [4] => 6
)
Array
(
    [0] => 6
    [1] => 5
    [2] => 4
    [3] => 3
    [4] => 2
)

*/

快速排序

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

优点:极快，数据移动少.

缺点：不稳定

function quickSort(array $arr): array
{
    $num = count($arr);
    if ($num <= 1) {
        return $arr;
    }

    $temp = $arr[0];
    $leftArr = [];
    $rightArr = [];

    for ($i = 1; $i < $num; $i++) {
        if ($temp < $arr[$i]) {
            $leftArr[] = $arr[$i];
        } else {
            $rightArr[] = $arr[$i];
        }
    }

    $leftArr = quickSort($leftArr);
    $rightArr = quickSort($rightArr);

    return array_merge($leftArr, [$temp], $rightArr);
}

var_dump($arr, quickSort($arr));

/*
输出：

Array
(
    [0] => 3
    [1] => 5
    [2] => 2
    [3] => 4
    [4] => 6
)
Array
(
    [0] => 6
    [1] => 5
    [2] => 4
    [3] => 3
    [4] => 2
)

*/

选择排序

• 在数组中，选出最小的一个数与第一个位置的数交换。然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。

优点：数据移动次数已知为（n-1）次

缺点：比较次数多

function selectSort(array &$arr): void
{
    $num = count($arr);
    if ($num <= 1) {
        return;
    }

    for ($i = 0; $i < $num - 1; $i++) {

        $index = $i;

        for ($j = $i + 1; $j < $num; $j++) {

            if ($arr[$index] > $arr[$j]) {
                $index = $j;
            }

            if ($index != $i) {
                $temp = $arr[$index];
                $arr[$index] = $arr[$i];
                $arr[$i] = $temp;
            }
        }
    }

}

print_r($arr);
selectSort($arr);
print_r($arr);

/*
输出：

Array
(
    [0] => 3
    [1] => 5
    [2] => 2
    [3] => 4
    [4] => 6
)
Array
(
    [0] => 2
    [1] => 3
    [2] => 5
    [3] => 4
    [4] => 6
)
*/

插入排序

• 每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。

优点：稳定，快

缺点：比较次数不一定，比较次数越少，插入点后的数据移动越多，特别是当数据总量庞大的时候

function insertSort(array &$arr): void
{
    $num = count($arr);
    if ($num <= 1) {
        return;
    }

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

        $temp = $arr[$i];

        for ($j = $i - 1; $j >= 0; $j--) {

            if ($temp < $arr[$j]) {
                $arr[$j + 1] = $arr[$j];
                $arr[$j] = $temp;
            } else {
                break;
            }
        }
    }
}


print_r($arr);
insertSort($arr);
print_r($arr);

/*
输出：

Array
(
    [0] => 3
    [1] => 5
    [2] => 2
    [3] => 4
    [4] => 6
)
Array
(
    [0] => 2
    [1] => 3
    [2] => 5
    [3] => 4
    [4] => 6
)
*/

希尔排序

归并排序

堆排序

计数排序

桶排序

基数排序