常见的经典比较类排序算法有冒泡排序、选择排序、快速排序、插入排序、希尔排序。这几种排序中快速排序和希尔排序的平均时间复杂度都突破了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)
非比较类排序算法传送门：//www.greatytc.com/p/8de11b38ff18
