【比较类排序算法】冒泡排序、选择排序、快速排序、插入排序、希尔排

常见的经典比较类排序算法有冒泡排序、选择排序、快速排序、插入排序、希尔排序。这几种排序中快速排序和希尔排序的平均时间复杂度都突破了O(n^2)，主要得益于这两种排序每轮排序都对下一轮产生影响，而其余的排序如选择排序每轮排序只是单纯从数组中找出最值，而没有对下一次的数组排序做出贡献。
<输入的最好方式就是输出>，本着学习的态度表达一下自己浅显的理解。下面主要介绍每种算法的中心思想，具体的代码实现(PHP)，并分析对应的时间复杂度和空间复杂度。

1.冒泡排序

以升序为例（后面同理），冒泡排序的思路是：相邻两个元素进行比较实现左小右大，交换完一轮得到最大值位于最后一位，按这个方式交换n-1轮（n为元素总数，后面同理）即完成排序。

代码如下：

function bubbleSort(array $arr)
{
    $len = count($arr);
    for ($i = 0; $i < $len - 1; $i++) {
        for ($k = 0; $k < $len - 1 - $i; $k++) {
            //交换位置条件
            if ($arr[$k] > $arr[$k + 1]) {
                $tmp = $arr[$k];
                $arr[$k] = $arr[$k + 1];
                $arr[$k + 1] = $tmp;
            }
        }
    }
    return $arr;
}

记忆关键词： 左右交换、每轮最值、n-1轮
性能分析：时间复杂度O(n^2)，空间复杂度O(1)

2.选择排序

选择排序的思路是：从左边第1个元素开始，与右边剩下的数组元素进行比较，每一轮得到最小值位于左侧，总共比较n-1轮完成排序。

代码如下：

function selectSort(array $arr)
{
    $len = count($arr);
    for ($i = 0; $i < $len - 1; $i++) {
        $min = $arr[$i];//最小值
        $minIndex = $i;//最小值下标
        for ($k = $i + 1; $k < $len; $k++) {
            if ($min > $arr[$k]) {
                $min = $arr[$k];
                $minIndex = $k;
            }
        }
        //比较完一轮后，交换左侧位置的最小值
        $tmp = $arr[$i];
        $arr[$i] = $arr[$minIndex];
        $arr[$minIndex] = $tmp;
    }
    return $arr;
}

记忆关键词： 左元素、右数组、左侧累加最值
性能分析：时间复杂度O(n^2)，空间复杂度O(1)

3.快速排序

快速排序的核心思想是递归和二分，思路是：先将待排数组分为左右分区，并获得中间基准，使得左分区元素均小于中间基准，右分区元素均大于中间基准。同样地，左右两分区按照相同的方式，递归划分各自的左右分区，最后完成排序。
快速排序的关键在于中间基准的确定，方法是：取数组左边第一位作为初始基准，把它与右边剩下的所有元素比较，依次将小于该基准的元素进行替换并记录位置，最后把获取到的位置元素与初始基准元素交换，完成左右分区，返回该中间基准位置。

代码如下：

function quickSort(array $arr, $left = null, $right = null)
{
    $len = count($arr);
    //初始化左右下标位置
    $left = $left ?? 0;
    $right = $right ?? $len - 1;

    //递归条件
    if ($left < $right) {
        //获取中心基准
        $partitionIndex = getPartitionIndex($arr, $left, $right);
        //左分区递归
        $arr = quickSort($arr, $left, $partitionIndex - 1);
        //右分区递归
        $arr = quickSort($arr, $partitionIndex + 1, $right);
    }

    return $arr;
}

/**
 * 将数组进行左右分区，并返回中心基准位置
 * @param array $arr
 * @param int $left
 * @param int $right
 * @return int
 */
function getPartitionIndex(array &$arr, int $left, int $right)
{
    $pivot = $left;//初始基准
    $index = $left + 1;//初始化游标位置，中心基准交换位置的下一位
    for ($i = $index; $i <= $right; $i++) {
        //将元素与初始基准比较
        if ($arr[$i] < $arr[$pivot]) {
            //小于基准，与游标元素交换
            $tmp = $arr[$i];
            $arr[$i] = $arr[$index];
            $arr[$index++] = $tmp;//移动游标
        }
    }

    //比较结束获得中心基准位置，与初始基准交换
    $resultIndex = $index - 1;
    $tmp = $arr[$pivot];
    $arr[$pivot] = $arr[$resultIndex];
    $arr[$resultIndex] = $tmp;
    return $resultIndex;
}

记忆关键词： 二分、递归、左右分区，中间基准
性能分析：时间复杂度O(nlog2n)，因为利用二分递归进行排序，时间复杂度突破n^2；空间复杂度O(log2n)，与递归次数相关。

4.插入排序

插入排序的思路是：左边先构建有序数组(初始为左边第一个元素)，右边元素从其下一位开始与其比较，若大于其末位元素则直接在末尾插入，否则继续往左遍历比较，确认插入位置，最后交换插入，构建新的有序数组。右边元素依次按照该方式插入有序数组，完成排序。

代码如下：

function insertSort(array $arr)
{
    $len = count($arr);
    for ($i = 1; $i < $len; $i++) {
        $index = $i - 1;//左边数组末位元素
        $current = $arr[$i];//右边第一个元素
        //当前值遍历左边数组，进行比较
        while ($index >= 0 && $current < $arr[$index]) {
            $arr[$index + 1] = $arr[$index];//左边数组扩大，最大值右移
            $index--;//左边数组比较位往前移
        }
        //插入左边数组结果位置
        $arr[$index + 1] = $current;
    }
    return $arr;
}

记忆关键词： 左有序数组、右元素遍历、右移插入
性能分析：时间复杂度O(n^2)，由代码可看出右移次数越少，右元素扫描遍历的次数就越少（由此引出插入排序的改良版希尔排序），最好的时间复杂度是O(n); 空间复杂度O(1)。

5.希尔排序

希尔排序是插入排序的改良版，也称缩小增量排序。思路是：将待排数组，按照指定的增量进行分组，每组分别进行插入排序，由于每个分组都经过排序，从而导致整个数组宏观上相对有序。最后将整个数组再进行一次插入排序。因为前面分组排序对最后一次排序产生了积极影响，所以整体的排序速度得到提升。

代码如下：

function shellSort(array $arr)
{
    $len = count($arr);
    //增量确定，这里取数组长度一半;
    //增量gap即为分组数，每趟下来分组数减半，直到分组数为1进行最后一次插入排序
    for ($gap = intval($len / 2); $gap > 0; $gap = intval($gap / 2)) {
        //对gap个数组分别进行插入排序
        for ($i = $gap; $i < $len; $i++) {
            $current = $arr[$i];//当前比较值
            $index = $i;//游标位置
            //当前值与上一个值比较（因为按照gap分组，所以分组内上一个值为index-gap）
            while ($index - $gap >= 0 && $current < $arr[$index - $gap]) {
                $arr[$index] = $arr[$index - $gap];
                $index = $index - $gap;
            }
            $arr[$index] = $current;
        }
    }
    return $arr;
}

记忆关键词： 确定增量、分组插入排序、缩小增量
性能分析：时间复杂度:O(nlogn)~O(n^2)， 空间复杂度O(1)

非比较类排序算法传送门：https://www.jianshu.com/p/8de11b38ff18