PHP面试：尽可能多的说出你知道的排序算法

摘要：良好的排序算法具有进行最少的比较和交换的特征。冒泡排序是一个基于比较的排序算法，被认为是效率最低的排序算法之一。现在让我们使用实现冒泡排序算法。插入排序到目前为止，我们已经看到了两种基于比较的排序算法。

本文适合对于排序算法不太了解的新手同学观看，大佬直接忽略即可。因为考虑到连贯性，所以篇幅较长。老铁们看完需要大概一个小时，但是从入门到完全理解可能需要10个小时(哈哈哈，以我自己的经历来计算的)，所以各位老铁可以先收藏下来，同步更新在Github，本文引用到的所有算法的实现在这个地址，每天抽点时间理解一个排序算法即可。

我们的数据大多数情况下是未排序的，这意味着我们需要一种方法来进行排序。我们通过将不同元素相互比较并提高一个元素的排名来完成排序。在大多数情况下，如果没有比较，我们就无法决定需要排序的部分。在比较之后，我们还需要交换元素，以便我们可以对它们进行重新排序。良好的排序算法具有进行最少的比较和交换的特征。除此之外，还存在基于非比较的排序，这类排序不需要比较数据来进行排序。我们将在这篇文章中为各位老铁介绍这些算法。以下是本篇文章中我们将要讨论的一些排序算法：

Bubble sort

Insertion sort

Selection sort

Quick sort

Merge sort

Bucket sort

以上的排序可以根据不同的标准进行分组和分类。例如简单排序，高效排序，分发排序等。我们现在将探讨每个排序的实现和复杂性分析，以及它们的优缺点。

我们先看下本文提到的各类排序算法的时间空间复杂度以及稳定性。各位老铁可以点击这里了解更多。

冒泡排序是编程世界中最常讨论的一个排序算法，大多数开发人员学习排序的第一个算法。冒泡排序是一个基于比较的排序算法，被认为是效率最低的排序算法之一。冒泡排序总是需要最大的比较次数，平均复杂度和最坏复杂度都是一样的。

冒泡排序中，每一个待排的项目都会和剩下的项目做比较，并且在需要的时候进行交换。下面是冒泡排序的伪代码。

procedure bubbleSort(A: list of sortable items)
n = length(A)
for i = 0 to n inclusive do
 for j = 0 to n - 1 inclusive do
    if A[j] > A[j + 1] then
        swap(A[j + 1], A[j])
    end if
  end for
end for
end procedure

正如我们从前面的伪代码中看到的那样，我们首先运行一个外循环以确保我们迭代每个数字，内循环确保一旦我们指向某个项目，我们就会将该数字与数据集合中的其他项目进行比较。下图显示了对列表中的一个项目进行排序的单次迭代。假设我们的数据包含以下项目：20,45,93,67,10,97,52,88,33,92。第一次迭代将会是以下步骤：

有背景颜色的项目显示的是我们正在比较的两个项目。我们可以看到，外部循环的第一次迭代导致最大的项目存储在列表的最顶层位置。然后继续，直到我们遍历列表中的每个项目。现在让我们使用PHP实现冒泡排序算法。

我们可以使用PHP数组来表示未排序的数字列表。由于数组同时具有索引和值，我们根据位置轻松迭代每个项目，并将它们交换到合适的位置。

function bubbleSort(&$arr) : void
{
    $swapped = false;
    for ($i = 0, $c = count($arr); $i < $c; $i++) {
        for ($j = 0; $j < $c - 1; $j ++) {
            if ($arr[$j + 1] < $arr[$j]) {
                list($arr[$j], $arr[$j + 1]) = array($arr[$j + 1], $arr[$j]);
            }
        }
    }
}

对于第一遍，在最坏的情况下，我们必须进行n-1比较和交换。 对于第2次遍历，在最坏的情况下，我们需要n-2比较和交换。 所以，如果我们一步一步地写它，那么我们将看到：复杂度= n-1 + n-2 + ..... + 2 + 1 = n *（n-1）/ 2 = O(n2)。因此，冒泡排序的复杂性是O(n2)。 分配临时变量，交换，遍历内部循环等需要一些恒定的时间，但是我们可以忽略它们，因为它们是不变的。以下是冒泡排序的时间复杂度表，适用于最佳，平均和最差情况：

尽管冒泡排序的时间复杂度是O(n2)，但是我们可以使用一些改进的手段来减少排序过程中对数据的比较和交换次数。最好的时间复杂度是O(n)是因为我们至少要一次内部循环才可以确定数据已经是排好序的状态。

冒泡排序最重要的一个方面是，对于外循环中的每次迭代，都会有至少一次交换。如果没有交换，则列表已经排序。我们可以利用它改进我们的伪代码

procedure bubbleSort(A: list of sortable items)
    n = length(A)
    for i = 1 to n inclusive do
        swapped = false
        for j = i to n - 1 inclusive do
            if A[j] > A[j + 1] then
                swap(A[j], A[j + 1])
                swapped = true
            endif
        end for
        if swapped = false
            break
        endif
    end for
end procedure
    

正如我们所看到的，我们现在为每个迭代设置了一个标志为false，我们期望在内部迭代中，标志将被设置为true。如果内循环完成后标志仍然为假，那么我们可以打破外循环。

function bubbleSort(&$arr) : void
{
    for ($i = 0, $c = count($arr); $i < $c; $i++) {
        $swapped = false;
        for ($j = 0; $j < $c - 1; $j++) {
            if ($arr[$j + 1] < $arr[$j]) {
                list($arr[$j], $arr[$j + 1]) = array($arr[$j + 1], $arr[$j]);
                $swapped = true;
            }
        }

        if (!$swapped) break; //没有发生交换，算法结束
    }
}

我们还发现，在第一次迭代中，最大项放置在数组的右侧。在第二个循环，第二大的项将位于数组右侧的第二个。我们可以想象出来在每次迭代之后，第i个单元已经存储了已排序的项目，不需要访问该索引和
做比较。因此，我们可以从内部迭代减少迭代次数并减少比较。这是我们的第二个改进的伪代码

procedure bubbleSort(A: list of sortable items)
    n = length(A)
    for i = 1 to n inclusive do
        swapped = false
        for j = 1 to n - i - 1 inclusive do
            if A[j] > A[j + 1] then
                swap(A[j], A[j + 1])
                swapped = true
            endif
        end for
        if swapped = false
            break
        end if
    end for
end procedure
   

下面的是PHP的实现

function bubbleSort(&$arr) : void
{
    
    for ($i = 0, $c = count($arr); $i < $c; $i++) {
        $swapped = false;
        for ($j = 0; $j < $c - $i - 1; $j++) {
            if ($arr[$j + 1] < $arr[$j]) {
                list($arr[$j], $arr[$j + 1]) = array($arr[$j + 1], $arr[$j]);
                $swapped = true;
            }

            if (!$swapped) break; //没有发生交换，算法结束
        }
    }
}

我们查看代码中的内循环，唯一的区别是$j < $c - $i - 1；其他部分与第一次改进一样。因此，对于20、45、93、67、10、97、52、88、33、92, 我们可以很认为，在第一次迭代之后，顶部数字97将不被考虑用于第二次迭代比较。同样的情况也适用于93，将不会被考虑用于第三次迭代。

我们看看前面的图，脑海中应该马上想到的问题是“92不是已经排序了吗？我们是否需要再次比较所有的数字？是的，这是一个好的问题。我们完成了内循环中的最后一次交换后可以知道在哪一个位置，之后的数组已经被排序。因此，我们可以为下一个循环设置一个界限，伪代码是这样的：

procedure bubbleSort(A: list of sortable items)
    n = length(A)
    bound = n - 1
    for i = 1 to n inclusive do
        swapped = false
        bound = 0
        for j = 1 to bound inclusive do
            if A[j] > A[j + 1] then
                swap(A[j], A[j + 1])
                swapped = true
                newbound = j
            end if
        end for
        bound = newbound
        if swapped = false
            break
        endif
    end for
end procedure
   

这里，我们在每个内循环完成之后设定边界，并且确保我们没有不必要的迭代。下面是PHP代码：

function bubbleSort(&$arr) : void
{
    $swapped = false;
    $bound = count($arr) - 1;
    for ($i = 0, $c = count($arr); $i < $c; $i++) {
        for ($j = 0; $j < $bound; $j++) {
            if ($arr[$j + 1] < $arr[$j]) {
                list($arr[$j], $arr[$j + 1]) = array($arr[$j + 1], $arr[$j]);
                $swapped = true;
                $newBound = $j;
            }
        }
        $bound = $newBound;
        if (!$swapped) break; //没有发生交换，算法结束
    }
}

选择排序是另一种基于比较的排序算法，它类似于冒泡排序。最大的区别是它比冒泡排序需要更少的交换。在选择排序中，我们首先找到数组的最小/最大项并将其放在第一位。如果我们按降序排序，那么我们将从数组中获取的是最大值。对于升序，我们获取的是最小值。在第二次迭代中，我们将找到数组的第二个最大值或最小值，并将其放在第二位。持续到我们把每个数字放在正确的位置。这就是所谓的选择排序，选择排序的伪代码如下：

procedure  selectionSort( A : list of sortable items)
    n = length(A)
    for i = 1 to n inclusive do
        min  =  i
        for j = i + 1 to n inclusive do
            if  A[j] < A[min] then
                min = j 
            end if
        end  for

        if min != i
            swap(a[i], a[min])
        end if
    end  for
end procedure

看上面的算法，我们可以发现，在外部循环中的第一次迭代之后，第一个最小项被存储在第一个位置。在第一次迭代中，我们选择第一个项目，然后从剩下的项目（从2到n）找到最小值。我们假设第一个项目是最小值。我们找到另一个最小值，我们将标记它的位置，直到我们扫描了剩余的列表并找到新的最小最小值。如果没有找到最小值，那么我们的假设是正确的，这确实是最小值。如下图：

正如我们在前面的图中看到的，我们从列表中的第一个项目开始。然后，我们从数组的其余部分中找到最小值10。在第一次迭代结束时，我们只交换了两个地方的值（用箭头标记）。因此，在第一次迭代结束时，我们得到了的数组中得到最小值。然后，我们指向下一个数字45，并开始从其位置的右侧找到下一个最小的项目，我们从剩下的项目中找到了20（如两个箭头所示）。在第二次迭代结束时，我们将第二个位置的值和从列表的剩余部分新找到的最小位置交换。这个操作一直持续到最后一个元素，在过程结束时，我们得到了一个排序的列表，下面是PHP代码的实现。

function selectionSort(&$arr)
{
    $count = count($arr);

    //重复元素个数-1次
    for ($j = 0; $j <= $count - 1; $j++) {
        //把第一个没有排过序的元素设置为最小值
        $min = $arr[$j];
        //遍历每一个没有排过序的元素
        for ($i = $j + 1; $i < $count; $i++) {
            //如果这个值小于最小值
            if ($arr[$i] < $min) {
                //把这个元素设置为最小值
                $min = $arr[$i];
                //把最小值的位置设置为这个元素的位置
                $minPos = $i;
            }
        }
        //内循环结束把最小值和没有排过序的元素交换
        list($arr[$j], $arr[$minPos]) = [$min, $arr[$j]];
    }
    
}

选择排序看起来也类似于冒泡排序，它有两个for循环，从0到n。冒泡排序和选择排序的区别在于，在最坏的情况下，选择排序使交换次数达到最大n - 1，而冒泡排序可以需要 n * n 次交换。在选择排序中，最佳情况、最坏情况和平均情况具有相似的时间复杂度。

到目前为止，我们已经看到了两种基于比较的排序算法。现在，我们将探索另一个排序算法——插入排序。与刚才看到的其他两个排序算法相比，它有最简单的实现。如果项目的数量较小，插入排序优于冒泡排序和选择排序。如果数据集很大，就像冒泡排序一样就变得效率低下。插入排序的工作原理是将数字插入到已排序列表的正确位置。它从数组的第二项开始，并判断该项是否小于当前值。如果是这样，它将项目转移，并将较小的项目存储在其正确的位置。然后，它移动到下一项，并且相同的原理继续下去，直到整个数组被排序。

procedure insertionSort(A: list of sortable items)
    n length(A)
    for i=1 to n inclusive do
        key = A[i]
        j = i - 1
        while j >= 0 and A[j] > key do
            A[j+1] = A[j]
            j--
        end while
        A[j + 1] = key
    end for
end procedure

假如我们有下列数组，元素是：20 45 93 67 10 97 52 88 33 92。我们从第二个项目45开始。现在我们将从45的左边第一个项目开始，然后到数组的开头，看看左边是否有大于45的值。由于只有20，所以不需要插入，目前两项(20, 45)被排序。现在我们将指针移到93，从它再次开始，比较从45开始，由于45不大于93，我们停止。现在，前三项（20, 45, 93）已排序。接下来，对于67，我们从数字的左边开始比较。左边的第一个数字是93，它较大，所以必须移动一个位置。我们移动93到67的位置。然后，我们移动到它左边的下一个项目45。45小于67，不需要进一步的比较。现在，我们先将93移动到67的位置，然后我们插入67的到93的位置。继续如上操作直到整个数组被排序。下图说明在每个步骤中使用插入排序的直到完全排序过程。

function insertionSort(array &$arr)
{
    $len = count($arr);
    for ($i = 1; $i < $len; $i++) {
        $key = $arr[$i];
        $j = $i - 1;

        while ($j >= 0 && $arr[$j] > $key) {
            $arr[$j + 1] = $arr[$j];
            $j--;
        }
        $arr[$j + 1] = $key;
    }
}

插入排序具有与冒泡排序相似的时间复杂度。与冒泡排序的区别是交换的数量远低于冒泡排序。

到目前为止，我们已经了解了每次对完整列表进行排序的一些排序算法。我们每次都需要应对一个比较大的数字集合。我们可以设法使数据集合更小，从而解决这个问题。分治思想对我们有很大帮助。用这种方法，我们将一个问题分成两个或多个子问题或集合，然后在组合子问题的所有结果以获得最终结果。这就是所谓的分而治之方法，分而治之方法可以让我们有效地解决排序问题，并降低算法的复杂度。最流行的两种排序算法是合并排序和快速排序，它们应用分治算法对数据进行排序，因此被认为是最好的排序算法。

正如我们已经知道的，归并排序应用分治方法来解决排序问题，我们用法两个过程来解决这个问题。第一个是将问题集划分为足够小的问题，以便容易地求解，然后将这些结果结合起来。我们将用递归方法来完成分治部分。下面的图显示了如何采用分治的方法。

基于前面的图像，我们现在可以开始准备我们的代码，它将有两个部分。

/**
 * 归并排序
 * 核心：两个有序子序列的归并(function merge)
 * 时间复杂度任何情况下都是 O(nlogn)
 * 空间复杂度 O(n)
 * 发明人: 约翰·冯·诺伊曼
 * 速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列
 * 一般不用于内(内存)排序，一般用于外排序
 */

function mergeSort($arr)
{
    $lenght = count($arr); 
    if ($lenght == 1) return $arr;
    $mid = (int)($lenght / 2);

    //把待排序数组分割成两半
    $left = mergeSort(array_slice($arr, 0, $mid));
    $right = mergeSort(array_slice($arr, $mid));

    return merge($left, $right);
}

function merge(array $left, array $right)
{
    //初始化两个指针
    $leftIndex = $rightIndex = 0;
    $leftLength = count($left);
    $rightLength = count($right);
    //临时空间
    $combine = [];

    //比较两个指针所在的元素
    while ($leftIndex < $leftLength && $rightIndex < $rightLength) {
        //如果左边的元素大于右边的元素，就将右边的元素放在多带带的数组，并将右指针向后移动
        if ($left[$leftIndex] > $right[$rightIndex]) {
            $combine[] = $right[$rightIndex];
            $rightIndex++;
        } else {
            //如果右边的元素大于左边的元素，就将左边的元素放在多带带的数组，并将左指针向后移动
            $combine[] = $left[$leftIndex];
            $leftIndex++;
        }
    }

    //右边的数组全部都放入到了返回的数组，然后把左边数组的值放入返回的数组
    while ($leftIndex < $leftLength) {
        $combine[] = $left[$leftIndex];
        $leftIndex++;
    }

    //左边的数组全部都放入到了返回的数组，然后把右边数组的值放入返回的数组
    while ($rightIndex < $rightLength) {
        $combine[] = $right[$rightIndex];
        $rightIndex++;
    }

    return $combine;
}

我们划分数组，直到它达到1的大小。然后，我们开始使用合并函数合并结果。在合并函数中，我们有一个数组来存储合并的结果。正因为如此，合并排序实际上比我们迄今所看到的其他算法具有更大的空间复杂度。

由于归并排序遵循分而治之的方法，所以我们必须解决这两个复杂问题。对于n个大小的数组，我们首先需要将数组分成两个部分，然后合并它们以得到n个大小的数组。我们可以看下面的示意图

解决每一层子问题需要的时间都是cn，假设一共有l层，那么总的时间复杂度会是ln。因为一共有logn + 1
层，那么结果就是 cn(logn + 1)。我们删除常数阶和线性阶，最后的结果可以得出时间复杂度就是O(nlog2n)。

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

function qSort(array &$arr, int $p, int $r)
{
    if ($p < $r) {
        $q = partition($arr, $p, $r);
        qSort($arr, $p, $q);
        qSort($arr, $q + 1, $r);
    }
}

function partition(array &$arr, int $p, int $r)
{
    $pivot = $arr[$p];
    $i = $p - 1;
    $j = $r + 1;

    while (true) {
        do {
            $i++;
        } while ($arr[$i] < $pivot);

        do {
            $j--;
        } while ($arr[$j] > $pivot);

        if ($i < $j) {
            list($arr[$i], $arr[$j]) = [$arr[$j], $arr[$i]];
        } else {
            return $j;
        }

    }
}

最坏情况下快速排序具有与冒泡排序相同的时间复杂度，pivot的选取非常重要。下面是快速排序的复杂度分析。

对于快速排序的优化，有兴趣的老铁可以点击这里查看。

桶排序 (Bucket sort)或所谓的箱排序，工作的原理是将数组分到有限数量的桶里。每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。

/**
 * 桶排序
 * 不是一种基于比较的排序
 * T(N, M) = O(M + N) N是带排序的数据的个数，M是数据值的数量
 * 当 M >> N 时，需要考虑使用基数排序
 */

function bucketSort(array &$data)
{
    $bucketLen = max($data) - min($data) + 1;
    $bucket = array_fill(0, $bucketLen, []);

    for ($i = 0; $i < count($data); $i++) {
        array_push($bucket[$data[$i] - min($data)], $data[$i]);
    }

    $k = 0;

    for ($i = 0; $i < $bucketLen; $i++) {
        $currentBucketLen = count($bucket[$i]);

        for ($j = 0; $j < $currentBucketLen; $j++) {
            $data[$k] = $bucket[$i][$j];
            $k++;
        }
    }
}

基数排序的PHP实现，有兴趣的同学同样可以访问这个页面来查看。

桶排序的时间复杂度优于其他基于比较的排序算法。以下是桶排序的复杂性

PHP有丰富的预定义函数库，也包含不同的排序函数。它有不同的功能来排序数组中的项目，你可以选择按值还是按键/索引进行排序。在排序时，我们还可以保持数组值与它们各自的键的关联。下面是这些函数的总结

对于sort()、rsort()、ksort()、krsort()、asort()以及 arsort()下面的常量可以使用

SORT_REGULAR - 正常比较单元（不改变类型）

SORT_NUMERIC - 单元被作为数字来比较

SORT_STRING - 单元被作为字符串来比较

SORT_LOCALE_STRING - 根据当前的区域（locale）设置来把单元当作字符串比较，可以用 setlocale() 来改变。

SORT_NATURAL - 和 natsort() 类似对每个单元以“自然的顺序”对字符串进行排序。 PHP 5.4.0 中新增的。

SORT_FLAG_CASE - 能够与 SORT_STRING 或 SORT_NATURAL 合并（OR 位运算），不区分大小写排序字符串。

本文引用到的所有算法的实现在这个地址，主要内容是使用PHP语法总结基础的数据结构和算法。欢迎各位老铁收藏～