十种排序算法详解

程序 = 数据结构 + 算法

在我们生活的这个世界中到处都是被排序过的。站队的时候会按照身高排序，考试的名次需要按照分数排序，网上购物的时候会按照价格排序，电子邮箱中的邮件按照时间排序……总之很多东西都需要排序，可以说排序是无处不在。

下面会分别讲解各种常见排序算法的原理以及使用该算法将以下数组按照从小到大进行排序的代码实现

<?php
    $demo_arr = [78, 34, 54, 10, 2, 10, 23, 1];

推荐这个以动画形式展现算法的网站： VisuAlgo – visualising data structures and algorithms through animation，可以查看具体排序的过程。

冒泡排序
简单选择排序
快速排序
直接插入排序
归并排序
堆排序
桶排序
基数排序
希尔排序（插入排序的改进版）
计数排序
总结

一、冒泡排序

介绍：

冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地走访要排序的数列，一次比较两个数据元素，如果顺序不对则进行交换，并一直重复这样的走访操作，直到没有要交换的数据元素为止。冒泡排序的思想就是在每次遍历一遍未排序的数列之后，将一个数据元素浮上去（也就是排好了一个数据）。

步骤：

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

这个算法让我想起了小时候在操场排队跑步，老师总是说：“高的站前面，低的站后面”。我们一开始并不一定会站到准确的位置上，接着老师又说：“你比前面的高，和前面的换换，还高，再和前面换换”，就这样找到了自己的位置。

冒泡排序的特点及性能：

通过冒泡排序的算法思想，我们发现冒泡排序算法在每轮排序中会使一个元素排到一端，也就是最终需要 n-1 轮这样的排序（n 为待排序的数列的长度），而在每轮排序中都需要对相邻的两个元素进行比较，在最坏的情况下，每次比较之后都需要交换位置，所以这里的时间复杂度是 O(n²)。其实冒泡排序在最好的情况下，时间复杂度可以达到 O(n)，这当然是在待排序的数列有序的情况下。在待排序的数列本身就是我们想要的排序结果时，时间复杂度的确是 O(n)，因为只需要一轮排序并且不用交换。但是实际上这种情况很少，所以冒泡排序的平均时间复杂度是 O(n²)。

对于空间复杂度来说，冒泡排序用到的额外的存储空间只有一个，那就是用于交换位置的临时变量，其他所有操作都是在原有待排序列上处理的，所以空间复杂度为 O(1)。

冒泡排序是稳定的，因为在比较过程中，只有后一个元素比前面的元素大时才会对它们交换位置并向上冒出，对于同样大小的元素，是不需要交换位置的，所以对于同样大小的元素来说，相对位置是不会改变的。

时间复杂度：

最好的情况为 O(n), 最坏的情况是 O(n^2)

代码示例：

<?php
function bubble_sort($list) {
    $len = count($list);
    
    for($i = 0; $i < $len - 1; $i++) {
        for($k = 0; $k < $len - $i - 1; $k++) {
            if($list[$k] > $list[$k + 1]) {
                $tmp = $list[$k + 1];
                $list[$k + 1] = $list[$k];
                $list[$k] = $tmp;
            }
        }
    }

    return $list;
}

$list = [78, 34, 54, 10, 2, 10, 23, 1];
echo "<pre>";
print_r(bubble_sort($list));
echo "</pre>";

优点：比较简单，空间复杂度较低，稳定

缺点：时间复杂度太高，效率低

改进版：

我们发现当第一次外层循环完成后，排序就完成了。后面的循环只有比较，而没有交换。
当一次外层循环中，相邻的元素没有发生交换，就说明数组已经是有序的了，这时可以跳出循环。
这样，我们可以设置一个布尔变量，记录一次外层循环中是否发生交换，如果未发生交换，算法就返回。

改进的冒泡排序代码：

<?php
function bubble_sort($list) {
    $len = count($list);
    for ($i = 0; $i < $len - 1; $i++) {
        $swapped = 0;
        for ($j = 0; $j < $len - $i - 1; $j++) {
            if ($list[$j] > $list[$j + 1]) {
                $swapped = 1;
                $tmp = $list[$j + 1];
                $list[$j + 1] = $list[$j];
                $list[$j] = $tmp;
            }
        }
        if ($swapped == 0) {
            return $list;
        }
    }
    return $list;
}

$list = [78, 34, 54, 10, 2, 10, 23, 1];
echo "<pre>";
print_r(bubble_sort($list));
echo "</pre>";

按照改进的算法，对于一个已经有序的数组，算法完成第一次外层循环后就会返回。
实际上只发生了 N – 1次比较，所以最好的情况下，该算法复杂度是O(N)。

二、简单选择排序

介绍：

选择排序(Selection sort)是一种简单直观的排序算法。
对于具有 n 个记录的无序表遍历 n-1 次，第 i 次从无序表中第 i 个记录开始，找出后序关键字中最小的记录，然后放置在第 i 的位置上。

步骤：

首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。以此类推，直到所有元素均排序完毕。

选择排序的特点及性能：

时间复杂度：

O(n^2)

代码示例：

<?php
function select_sort($arr) {
    $len = count($arr);

    for ($i = 0; $i < $len; $i++) {
        $p = $i;

        for ($j = $i + 1; $j < $len; $j++) {
            if ($arr[$p] > $arr[$j]) {
                $p = $j;
            }
        }
        if ($p != $i) {
            $tmp = $arr[$p];
            $arr[$p] = $arr[$i];
            $arr[$i] = $tmp;
        }
        
    }

    return $arr;
}

$arr = [78, 34, 54, 10, 2, 10, 23, 1];
echo "<pre>";
print_r(select_sort($arr));
echo "</pre>";

优点：尽管与冒泡排序同为O(n^2),但简单选择排序的性能要略优于冒泡排序

缺点：比较次数多

三、快速排序

介绍：

快速排序（Quicksort）是由东尼·霍尔所发展的一种排序算法。采用分而治之的策略。

在平均状况下，排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来，且在大部分真实世界的数据，可以决定设计的选择，减少所需时间的二次方项之可能性。

步骤：

1．先从数列中取出一个数作为基准数 pivot。

2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

3．再对左右区间重复第二步，直到各区间只有一个数。

假设我们现在对“6 1 2 7 9 3 4 5 10 8”这个 10 个数进行排序。首先在这个序列中随便找一个数作为基准数（不要被这个名词吓到了，就是一个用来参照的数，待会你就知道它用来做啥的了）。为了方便，就让第一个数 6 作为基准数吧。接下来，需要将这个序列中所有比基准数大的数放在 6 的右边，比基准数小的数放在 6 的左边，类似下面这种排列。

3 1 2 5 4 6 9 7 10 8

时间复杂度：

O(nlogn)

代码示例：

<?php
function quick_sort( $arr ) {
    //判断参数是否是一个数组
    if ( !is_array( $arr ) ) return false;
    //递归出口:数组长度为1，直接返回数组
    $length = count( $arr );
    if ( $length <= 1 ) return $arr;
    //数组元素有多个, 则定义两个空数组
    $left = $right = [];
    //使用for循环进行遍历，把第一个元素当做比较的对象
    for ( $i = 1; $i < $length; $i++ ) {
        //判断当前元素的大小
        if ( $arr[$i] < $arr[0] ) {
            $left[] = $arr[$i];
        } 
        else {
            $right[] = $arr[$i];
        }
    }
    //递归调用
    $left = quick_sort( $left );
    $right = quick_sort( $right );
    //将所有的结果合并
    return array_merge( $left, array($arr[0]), $right );
}
$arr = [78, 34, 54, 10, 2, 10, 23, 1];
echo "<pre>";
print_r(quick_sort($arr));
echo "</pre>";

优点：极快，数据移动少

缺点：不稳定

四、直接插入排序

介绍：

插入排序（Insertion Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

步骤：

从第一个元素开始，该元素可以认为已经被排序
取出下一个元素，在已经排序的元素序列中从后向前扫描（因为前面的已经是排好序的）
如果该元素（已排序）大于新元素，将该元素移到下一位置
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到该位置中
重复步骤2

时间复杂度：

O(n^2)

代码示例：

<?php
function insertSort($arr) {
    $len = count($arr);

    for ($i = 1; $i < $len; $i++) {
        $tmp = $arr[$i];
        for ($j = $i - 1; $j >= 0; $j--) {
            if ($tmp < $arr[$j]) {
                $arr[$j + 1] = $arr[$j];
                $arr[$j] = $tmp;
            } else {
                break;
            }
        }
    }
    return $arr;
}

$arr = [78, 34, 54, 10, 2, 10, 23, 1];
echo "<pre>";
print_r(insertSort($arr));
echo "</pre>";

五、归并排序

介绍：

归并排序是建立在归并操作上的一种有效的排序算法。

归并排序将待排序的序列分成若干组，保证每组都有序，然后再进行合并排序，最终使整个序列有序。

该算法是采用分治法的一个非常典型的应用。

步骤：

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
设定两个指针，最初位置分别为两个已经排序序列的起始位置；
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
重复步骤 3 直到某一指针达到序列尾；
将另一序列剩下的所有元素直接复制到合并序列尾。

时间复杂度：

O(nlogn)

代码示例：

<?php
/**
 * 归并排序
 *
 * @param array $lists
 * @return array
 */
function merge_sort(array $lists) {
    $n = count($lists);
    if ($n <= 1) {
        return $lists;
    }
    $left = merge_sort(array_slice($lists, 0, floor($n / 2)));
    $right = merge_sort(array_slice($lists, floor($n / 2)));
    $lists = merge($left, $right);
    return $lists;
}

function merge(array $left, array $right) {
    $lists = [];
    $i = $j = 0;
    while ($i < count($left) && $j < count($right)) {
        if ($left[$i] < $right[$j]) {
            $lists[] = $left[$i];
            $i++;
        } else {
            $lists[] = $right[$j];
            $j++;
        }
    }
    $lists = array_merge($lists, array_slice($left, $i));
    $lists = array_merge($lists, array_slice($right, $j));
    return $lists;
}

$lists = [78, 34, 54, 10, 2, 10, 23, 1];
echo "<pre>";
print_r(merge_sort($lists));
echo "</pre>";

六、堆排序

介绍：

堆排序是指利用堆这种数据结构所设计的一种排序算法。

堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

基本思想：

输入：一系列的无序元素（比如说，数字）组成的输入数组A

经过：堆排序的过程可以具体分为三步，创建堆，调整堆，堆排序。

创建堆，以数组的形式将堆中所有的数据重新排序，使其成为最大堆/最小堆。

调整堆，调整过程需要保证堆序性质：在一个二叉堆中任意父节点大于其子节点。

堆排序，取出位于堆顶的第一个数据（最大堆则为最大数，最小堆则为最小数），放入输出数组B 中，再将剩下的对作调整堆的迭代/重复运算直至输入数组 A中只剩下最后一个元素。

输出：输出数组B，里面包含的元素都是A 中的但是已经按照要求排好了顺序

步骤：

创建一个堆H[0..n-1]；
把堆首（最大值）和堆尾互换；
把堆的尺寸缩小1，并调用shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
重复步骤2，直到堆的尺寸为1。

堆中定义以下几种操作：

最大堆调整（Max Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
创建最大堆（Build Max Heap）：将堆中的所有数据重新排序
堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算

可视化堆排序

时间复杂度：

Ο(nlogn)

代码示例：

<?php
/**
 * 堆排序
 *
 * @param array $lists
 * @return array
 */
function heap_sort(array $lists) {
    $n = count($lists);
    build_heap($lists);
    while (--$n) {
        $val = $lists[0];
        $lists[0] = $lists[$n];
        $lists[$n] = $val;
        heap_adjust($lists, 0, $n);
        //echo "sort: " . $n . "\t" . implode(', ', $lists) . PHP_EOL;
    }
    return $lists;
}

function build_heap(array &$lists) {
    $n = count($lists) - 1;
    for ($i = floor(($n - 1) / 2); $i >= 0; $i--) {
        heap_adjust($lists, $i, $n + 1);
        //echo "build: " . $i . "\t" . implode(', ', $lists) . PHP_EOL;
    }
    //echo "build ok: " . implode(', ', $lists) . PHP_EOL;
}

function heap_adjust(array &$lists, $i, $num) {
    if ($i > $num / 2) {
        return;
    }
    $key = $i;
    $leftChild = $i * 2 + 1;
    $rightChild = $i * 2 + 2;

    if ($leftChild < $num && $lists[$leftChild] > $lists[$key]) {
        $key = $leftChild;
    }
    if ($rightChild < $num && $lists[$rightChild] > $lists[$key]) {
        $key = $rightChild;
    }
    if ($key != $i) {
        $val = $lists[$i];
        $lists[$i] = $lists[$key];
        $lists[$key] = $val;
        heap_adjust($lists, $key, $num);
    }
}

$lists = [78, 34, 54, 10, 2, 10, 23, 1];
echo "<pre>";
print_r(heap_sort($lists));
echo "</pre>";

七、桶排序

介绍：

桶排序 (Bucket sort)是将待排序的数据分割成许多buckets，然后每个bucket各自排序，或用不同的排序算法，或者递归的使用bucket sort算法。也是典型的分而治之（divide-and-conquer）的策略。

步骤：

找出待排序数组arr中的最大值max、最小值min；
设置一个定量的数组当作空桶，范围为min~max（min、max为步骤1求得的最小值、最大值）；
遍历待排序数组arr，计算每个元素arr[i]放的桶，把数据放到对应的桶里；
如果桶不为空，对桶中的数据进行排序；
遍历桶数组，把所有桶中排序好的元素放到一个新的数组里。

时间复杂度：

Ο(n)

代码示例：

<?php
function bucketSort($arr) {
    // 设置木桶
    $bucket = [];
    $min = min($arr);
    $max = max($arr);
    // 𝑏𝑢𝑐𝑘𝑒𝑡=𝑎𝑟𝑟𝑎𝑦𝑓𝑖𝑙𝑙(min, 𝑚𝑎𝑥−min + 1, 0);
    for ($m = $min; $m <= $max; $m++) {
        $bucket[$m] = 0;
    }
    // 将待排数据按照范围放到对应的木桶中
    $cnt = count($arr);
    for ($n = 0; $n < $cnt; $n++) {
        $bucket[$arr[$n]]++;
    }
    // 从木桶中拿出数据
    $result = [];
    for ($i = $min; $i <= $max; $i++) {
        if (($bucket[$i]) > 0) {
            for ($j = 1; $j <= $bucket[$i]; $j++) {
                $result[] = [$i];
            }
        }
    }
    // 处理数组
    $res = [];
    foreach ($result as $v) {
        $res[] = $v[0];
    }
    return $res;
}
 

$lists = [78, 34, 54, 10, 2, 10, 23, 1];
echo "<pre>";
print_r(bucketSort($lists));
echo "</pre>";

优点：桶排序是稳定的，是常见排序里最快的一种,比快排还要快…大多数情况下

缺点：不适用于数据比较松散的数列，桶排序非常快,但是同时也非常耗空间,基本上是最耗空间的一种排序算法

八、基数排序

介绍：

基数排序是一种非比较型整数排序算法，其原理是将整数按位数（如个位、十位、百位）切割成不同的数字，然后按每个位数分别比较。
由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

例如将数列 “78, 34, 54, 10, 2” 进行基数排序，首先按照十位数，将数列分为：”02, 10, 34, 54, 78″，如果十位数刚好出现多个，则再根据个位数进行单独的排序。

步骤：

将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零
从最低位开始，依次进行一次排序
从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列

时间复杂度：

O(n * k)

代码示例：

<?php
/**
 * 基数排序
 *
 * @param array $lists
 * @return array
 */
function radix_sort(array $lists) {
    $radix = 10;
    $max = max($lists);
    $k = ceil(log($max, $radix));
    if ($max == pow($radix, $k)) {
        $k++;
    }
    for ($i = 1; $i <= $k; $i++) {
        $newLists = array_fill(0, $radix, []);
        for ($j = 0; $j < count($lists); $j++) {
            $key = $lists[$j] / pow($radix, $i - 1) % $radix;
            $newLists[$key][] = $lists[$j];
        }
        $lists = [];
        for ($j = 0; $j < $radix; $j++) {
            $lists = array_merge($lists, $newLists[$j]);
        }
    }
    return $lists;
}

$lists = [78, 34, 54, 10, 2];
echo "<pre>";
print_r(radix_sort($lists));
echo "</pre>";

九、希尔排序（插入排序的改进版）

介绍：

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

步骤：

选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
按增量序列个数 k，对序列进行 k 趟排序；
每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

时间复杂度：

O(nlogn)

代码示例：

<?php
function shell_sort($lists) {
    $len = count($lists);
    $temp = 0;
    $gap = 1;
    while($gap < $len / 3) {
        $gap = $gap * 3 + 1;
    }
    for ($gap; $gap > 0; $gap = floor($gap / 3)) {
        for ($i = $gap; $i < $len; $i++) {
            $temp = $lists[$i];
            for ($j = $i - $gap; $j >= 0 && $lists[$j] > $temp; $j -= $gap) {
                $lists[$j+$gap] = $lists[$j];
            }
            $lists[$j+$gap] = $temp;
        }
    }
    return $lists;
}

$lists = [78, 34, 54, 10, 2];
echo "<pre>";
print_r(shell_sort($lists));
echo "</pre>";

十、计数排序

介绍：

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

步骤：

花 O(n) 的时间扫描一下整个序列 A，获取最小值 min 和最大值 max
开辟一块新的空间创建新的数组 B，长度为 ( max – min + 1)
数组 B 中 index 的元素记录的值是 A 中某元素出现的次数
最后输出目标整数序列，具体的逻辑是遍历数组 B，输出相应元素以及对应的个数

时间复杂度：

O (n + k)

代码示例：

<?php
function counting_sort($arr, $maxValue = null) {
    if ($maxValue === null) {
        $maxValue = max($arr);
    }
    for ($m = 0; $m < $maxValue + 1; $m++) {
        $bucket[] = null;
    }

    $arrLen = count($arr);
    for ($i = 0; $i < $arrLen; $i++) {
        if (!array_key_exists($arr[$i], $bucket)) {
            $bucket[$arr[$i]] = 0;
        }
        $bucket[$arr[$i]]++;
    }

    $sortedIndex = 0;
    foreach ($bucket as $key => $len) {
        if($len !== null){
            for($j = 0; $j < $len; $j++){
                $arr[$sortedIndex++] = $key;
            }
        }
    }

    return $arr;
}

$lists = [78, 34, 54, 10, 2, 10, 23, 1];
echo "<pre>";
print_r(counting_sort($lists));
echo "</pre>";

总结

各种排序的稳定性，时间复杂度、空间复杂度、稳定性总结如下图：

O(n)这样的标志叫做渐近时间复杂度,是个近似值.各种渐近时间复杂度由小到大的顺序如下

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

一般时间复杂度到了2^n(指数阶)及更大的时间复杂度,这样的算法我们基本上不会用了,太不实用了.比如递归实现的汉诺塔问题算法就是O(2^n).

平方阶(n^2)的算法是勉强能用,而nlogn及更小的时间复杂度算法那就是非常高效的算法了啊.

最快的排序算法是桶排序

所有排序算法中最快的应该是桶排序(很多人误以为是快速排序,实际上不是.不过实际应用中快速排序用的多)但桶排序一般用的不多,因为有几个比较大的缺陷.

1.待排序的元素不能是负数,小数.

2.空间复杂度不确定,要看待排序元素中最大值是多少.

所需要的辅助数组大小即为最大元素的值.