预警
本文适合对于排序算法不太了解的新手同学观看，大佬直接忽略即可。因为考虑到连贯性，所以篇幅较长。老铁们看完需要大概一个小时，但是从入门到完全理解可能需要10个小时(哈哈哈，以我自己的经历来计算的)，所以各位老铁可以先收藏下来，同步更新在Github，本文引用到的所有算法的实现在这个地址：
https://github.com/xx19941215/light-tips
，每天抽点时间理解一个排序算法即可。
排序和他们的类型
我们的数据大多数情况下是未排序的，这意味着我们需要一种方法来进行排序。我们通过将不同元素相互比较并提高一个元素的排名来完成排序。在大多数情况下，如果没有比较，我们就无法决定需要排序的部分。在比较之后，我们还需要交换元素，以便我们可以对它们进行重新排序。良好的排序算法具有进行最少的比较和交换的特征。除此之外，还存在基于非比较的排序，这类排序不需要比较数据来进行排序。我们将在这篇文章中为各位老铁介绍这些算法。以下是本篇文章中我们将要讨论的一些排序算法：
-
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)。 分配临时变量，交换，遍历内部循环等需要一些恒定的时间，但是我们可以忽略它们，因为它们是不变的。以下是冒泡排序的时间复杂度表，适用于最佳，平均和最差情况：
|
best time complexity
|
Ω(n)
|
|
worst time complexity
|
O(n2)
|
|
average time complexity
|
Θ(n2)
|
|
space complexity (worst case)
|
O(1)
|
尽管冒泡排序的时间复杂度是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
次交换。在选择排序中，最佳情况、最坏情况和平均情况具有相似的时间复杂度。
|
best time complexity
|
Ω(n2)
|
|
worst time complexity
|
O(n2)
|
|
average time complexity
|
Θ(n2)
|
|
space complexity (worst case)
|
O(1)
|
插入排序
到目前为止，我们已经看到了两种基于比较的排序算法。现在，我们将探索另一个排序算法——插入排序。与刚才看到的其他两个排序算法相比，它有最简单的实现。如果项目的数量较小，插入排序优于冒泡排序和选择排序。如果数据集很大，就像冒泡排序一样就变得效率低下。插入排序的工作原理是将数字插入到已排序列表的正确位置。它从数组的第二项开始，并判断该项是否小于当前值。如果是这样，它将项目转移，并将较小的项目存储在其正确的位置。然后，它移动到下一项，并且相同的原理继续下去，直到整个数组被排序。
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;
}
}
插入排序的复杂度
插入排序具有与冒泡排序相似的时间复杂度。与冒泡排序的区别是交换的数量远低于冒泡排序。
|
best time complexity
|
Ω(n)
|
|
worst time complexity
|
O(n2)
|
|
average time complexity
|
Θ(n2)
|
|
space complexity (worst case)
|
O(1)
|
排序中的分治思想
到目前为止，我们已经了解了每次对完整列表进行排序的一些排序算法。我们每次都需要应对一个比较大的数字集合。我们可以设法使数据集合更小，从而解决这个问题。分治思想对我们有很大帮助。用这种方法，我们将一个问题分成两个或多个子问题或集合，然后在组合子问题的所有结果以获得最终结果。这就是所谓的分而治之方法，分而治之方法可以让我们有效地解决排序问题，并降低算法的复杂度。最流行的两种排序算法是合并排序和快速排序，它们应用分治算法对数据进行排序，因此被认为是最好的排序算法。
归并排序
正如我们已经知道的，归并排序应用分治方法来解决排序问题，我们用法两个过程来解决这个问题。第一个是将问题集划分为足够小的问题，以便容易地求解，然后将这些结果结合起来。我们将用递归方法来完成分治部分。下面的图显示了如何采用分治的方法。
基于前面的图像，我们现在可以开始准备我们的代码，它将有两个部分。
/**
* 归并排序
* 核心：两个有序子序列的归并(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++;
