参考博客：https://www.cnblogs.com/onepixel/articles/7674659.html
排序的分类脑图：
排序分类的脑图
另一种排序分类图：
排序分类图之2
)
一些重要的概念：
-
稳定性：
如果a原本在b前面，而a=b，排序之后a仍然在b的前面，则称该算法是稳定的，否则是不稳定的。 -
时间复杂度(T(n)):
对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律. -
空间复杂度(S(n)):
是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
1.冒泡排序
用冒泡基本概念的实现代码：
def bubble_sort(input_arr):
if not input_arr or len(input_arr) < 1:
return False
length = len(input_arr)
bottom_idx = 0
while bottom_idx < length - 1:
i = length - 1
while i > bottom_idx:
if input_arr[i] < input_arr[i - 1]:
tmp = input_arr[i]
input_arr[i] = input_arr[i - 1]
input_arr[i - 1] = tmp
i -= 1
bottom_idx += 1
return
优化点：
- 冒泡优化点1：如果一趟比较中，没有任何位置交换，则直接结束，这说明序列已经按照正确的顺序排列：
def bubble_sort_opt_1(input_arr):
"""
冒泡优化点1：如果一趟比较中，没有任何位置交换，则直接结束，这说明序列已经按照正确的顺序排列
:param input_arr:
:return:
"""
if not input_arr or len(input_arr) < 1:
return False
length = len(input_arr)
bottom_idx = 0
while bottom_idx < length - 1:
i = length - 1
is_exchange = False
while i > bottom_idx:
if input_arr[i] < input_arr[i - 1]:
tmp = input_arr[i]
input_arr[i] = input_arr[i - 1]
input_arr[i - 1] = tmp
is_exchange = True
i -= 1
if not is_exchange:
break
bottom_idx += 1
return
- 冒泡优化点2：如果一趟比较中，有位置交换，则标记第一次交换位置的地方，说明在这次交换之前的序列都是有序的。下一次循环直接从这个标记的位置开始
def bubble_sort_opt_2(input_arr):
"""
冒泡优化点2：如果一趟比较中，有位置交换，则记录第一次交换位置的地方，说明这次交换之前的序列都是有序的，下一次循环直接从这个位置开始
:param input_arr:
:return:
"""
if not input_arr or len(input_arr) < 1:
return False
length = len(input_arr)
bottom_idx = 0
top_idx = length - 1
while bottom_idx < top_idx:
i = top_idx
is_exchange = False
# 用来标记第一次交换的位置
next_i = -1
while i > bottom_idx:
if input_arr[i] < input_arr[i - 1]:
tmp = input_arr[i]
input_arr[i] = input_arr[i - 1]
input_arr[i - 1] = tmp
is_exchange = True
if next_i < 0:
next_i = i
i -= 1
if not is_exchange:
break
bottom_idx += 1
if next_i > 0:
top_idx = next_i
bottom_idx += 1
return
特点：
| 最小T(n) | 最大T(n) | 平均T(n) | 空间复杂度 | 是否稳定 | 适用场景 |
|---|---|---|---|---|---|
| O(n) | O(n^2) | O(n^2) | O(1) | 稳定 | 入门算法 |
2.快速排序
快排是经典的分治思想的排序，其中一个很重要的函数是partition函数，该函数作用是把一个乱序数组找到一个中枢值(pivot)，把整个数组调整成小于pivot的值和大于pivot的值分布于数组左右，并返回具体pivot的索引位置，时间复杂度为O(n)。
这个partition还可以应用于多种场合，比如无须数组求第K大的数字
代码如下：
def partition(arr, low, high):
if low > high:
return -1
pivot = arr[low]
left = low
right = high
while left < right:
while right > left and arr[right] > pivot:
right -= 1
arr[left] = arr[right]
# 注意，这里为什么用 “<=” ？ 如果用 “<” 可能会死循环，考虑如果 arr[right]==arr[left]==pivot
while left < right and arr[left] <= pivot:
left += 1
arr[right] = arr[left]
target_loc = left
arr[target_loc] = pivot
return target_loc
def qucik_sort_proxy(arr, low, high):
if low < high and low >= 0 and high >= 0:
middle = partition(arr, low, high)
qucik_sort_proxy(arr, low, middle - 1)
qucik_sort_proxy(arr, middle + 1, high)
def quick_sort(arr):
if not arr or len(arr) < 2:
return
qucik_sort_proxy(arr, 0, len(arr) - 1)
优化点
参考1：三种快排及四种优化方式
参考2：编程珠玑中的快速排序 优化 详细分析
- 快排优化点1：合理选择pivot
改变固定中枢值的选择：取三个数，取中间值作为中枢值(pivot) - 快排优化点2：混用快排和插入排序
当待排序序列的长度分割到一定大小后，使用插入排序，因为针对长度比较小的数组，快排的效率是不如插入排序的。根据统计结论得到的临界阈值是50左右(REF[3])，也有采用20的（REF[1]） - 快排优化点3：处理和pivot相等的值
把和pivot相等的值聚合在一起，递归或迭代操作时，摒除和pivot相等的值。 - 快排优化点4：尾递归优化
针对大数据量的数组，如果用递归方法，递归栈会非常大，可以用尾递归的方式，缩减堆栈深度，由原来的O(n)缩减为O(logn)。（其实这种优化编译器会自己优化，相比不使用优化的方法，时间几乎没有减少）
所谓尾递归的写法如下：
def qucik_sort_proxy(arr, low, high):
while low < high and low >= 0 and high >= 0:
middle = partition(arr, low, high)
qucik_sort_proxy(arr, low, middle - 1)
low = middle + 1
- 快排优化点5：递归改为迭代写法
迭代写法其实也是用栈保存low，high参数来模拟递归函数的操作，效率肯定比递归好，但是可读性完全没递归高
特点：
| 最小T(n) | 最大T(n) | 平均T(n) | 空间复杂度 | 是否稳定 | 适用场景 |
|---|---|---|---|---|---|
| O(nlogn) | O(n^2) | O(nlogn) | O(logn) | 不稳定 | 大数据量的内部排序中，被认为是最好的适用排序算法，最常用 |
最差情况下，快排退化为冒泡排序了，最大时间复杂度为O(n^2)，空间复杂度为O(n)，这里空间复杂度是递归栈所占用的内存空间。
3.直接插入排序
思想：将一个值插入到一个有序队列中，找到合适的坑位插入之。还是用自己感到舒服的语言吧。。
PHP代码：
/**
* 测试用例： null , false, '', [], [1],[1,2], [5,7,9,1,2,8,8]
* @param $arr
* @return bool
*/
function straight_insert_sort($arr) {
if (empty($arr) || !is_array($arr)) {
return false;
}
if (count($arr) < 2) {
return $arr;
}
$len = count($arr);
for ($i = 1; $i < $len; ++$i) {
// 将一个值插入到一个有序序列中
$tmpVal = $arr[$i];
$targetLoc = $i;
for ($j = $i; $j > 0; --$j) {
if ($tmpVal < $arr[$j - 1]) {
$targetLoc = $j - 1;
$arr[$j] = $arr[$j - 1];
} else {
break;
}
}
$arr[$targetLoc] = $tmpVal;
}
return $arr;
}
特点：
| 最小T(n) | 最大T(n) | 平均T(n) | 空间复杂度 | 是否稳定 | 适用场景 |
|---|---|---|---|---|---|
| O(n) | O(n^2) | O(n^2) | O(1) | 稳定 | 实现简单，在待排序数据量较小并且基本有序的情况下能获得很高的收益。因此常和快排、归并排序结合使用。 |
4. 希尔排序
参考：图解希尔排序
代码：
/**
* 希尔排序：步长从大到小，执行插入排序
* 测试用例： null , false, '', [], [1],[1,2], [5,7,9,1,2,8,8]
* @param $arr
* @return array|bool
*/
function shell_sort($arr) {
if (empty($arr) || !is_array($arr)) {
return false;
}
if (count($arr) < 2) {
return $arr;
}
$len = count($arr);
for ($gap = intval($len / 2); $gap > 0; $gap = intval($gap / 2)) {
for ($i = $gap; $i < $len; $i += $gap) {
// 将一个值插入到一个有序序列中
$tmpVal = $arr[$i];
$targetLoc = $i;
for ($j = $i; $j - $gap >= 0; $j -= $gap) {
if ($tmpVal < $arr[$j - $gap]) {
$targetLoc = $j - $gap;
$arr[$j] = $arr[$j - $gap];
} else {
break;
}
}
$arr[$targetLoc] = $tmpVal;
}
}
return $arr;
}
特点
| 最小T(n) | 最大T(n) | 平均T(n) | 空间复杂度 | 是否稳定 | 适用场景 |
|---|---|---|---|---|---|
| O(n) | O(n^2) | O(n^1.5) | O(1) | 稳定 | 是直接插入排序的一种优化，但是实现起来比较复杂，不常用 |
希尔排序也叫缩小增量排序，特点是先用大的增量把整个数组调整成一个基本有序的数组，最后执行一次直接插入排序，其时间复杂度依赖于增量的选取策略，综合网上的说法，比较牛的增量选取策略能让平均时间复杂度降低到O(n^1.5)左右。
5. 简单选择排序
思想是，每次都进行一趟子序列的比较，把最小或最大的元素选出来，和指定位置的元素交换。
PHP代码：
/**
* 简单选择排序：每一趟选择出最小的元素放到子序列的最前面
* 测试用例： null , false, '', [], [1],[1,2], [5,7,9,1,2,8,8]
* @param $arr
* @return array|bool
*/
function simple_selection_sort($arr) {
if (empty($arr) || !is_array($arr)) {
return false;
}
if (count($arr) < 2) {
return $arr;
}
$len = count($arr);
for ($i = 0; $i < $len - 1; ++$i) {
$targetLoc = $i;
$stdVal = $arr[$i];
for ($j = $i + 1; $j < $len; ++$j) {
if ($arr[$j] < $stdVal) {
$targetLoc = $j;
$stdVal = $arr[$j];
}
}
$arr[$targetLoc] = $arr[$i];
$arr[$i] = $stdVal;
}
return $arr;
}
特点
| 最小T(n) | 最大T(n) | 平均T(n) | 空间复杂度 | 是否稳定 | 适用场景 |
|---|---|---|---|---|---|
| O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 | 实现简单，但不适用于大数据量的排序 |
6.堆排序
参考：图解堆排序
堆排序的精髓在于堆创建和堆调整两个步骤，可以认为堆排序就是这两个步骤的组合封装，PHP代码：
/**
* 大顶堆的调整，自上而下调整顺序，满足大顶堆的特征
* @param $arr 堆数组
* @param $idx 当前调整位置的索引位置
* @param $maxIdx 这一次调整的堆数组的最大边界索引
* @return bool
*/
function justify_heap(&$arr, $idx, $maxIdx) {
$len = $maxIdx + 1;
while ($idx < $len) {
$leftIdx = 2 * $idx + 1;
$rightIdx = 2 * $idx + 2;
if ($leftIdx < $len && $rightIdx < $len) {
// 有左右孩子
$maxChildIdx = $arr[$leftIdx] > $arr[$rightIdx] ? $leftIdx : $rightIdx;
} else if ($leftIdx < $len && $rightIdx >= $len) {
// 只有左孩子
$maxChildIdx = $leftIdx;
} else {
// 左右孩子都无，是叶子节点
break;
}
if ($arr[$idx] > $arr[$maxChildIdx]) {
break;
} else {
$tmp = $arr[$idx];
$arr[$idx] = $arr[$maxChildIdx];
$arr[$maxChildIdx] = $tmp;
$idx = $maxChildIdx;
}
}
return true;
}
/**
* 构建大顶堆，本质是从中间节点开始，从下往上调整堆
* @param $arr
* @return bool
*/
function build_heap(&$arr) {
$len = count($arr);
if ($len < 1) {
return false;
}
$midIndex = intval($len / 2);
for ($i = $midIndex; $i >= 0; --$i) {
justify_heap($arr, $i, $len - 1);
}
return true;
}
/**
* 堆排序
* @param $arr
* @return array|bool
*/
function heap_sort($arr) {
if (empty($arr) || !is_array($arr)) {
return false;
}
$len = count($arr);
if ($len < 2) {
return $arr;
}
// 先构建大顶堆
build_heap($arr);
// 从最后一个元素开始，置换出最大的值，并且调整堆
for ($i = $len - 1; $i > 0; --$i) {
$tmp = $arr[0];
$arr[0] = $arr[$i];
$arr[$i] = $tmp;
justify_heap($arr, 0, $i - 1);
}
return $arr;
}
特点
| 最小T(n) | 最大T(n) | 平均T(n) | 空间复杂度 | 是否稳定 | 适用场景 |
|---|---|---|---|---|---|
| O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 | 时间复杂度比较均衡的O(nlogn)级别的排序，不会出现快排的最差情况下O(n^2)的时间复杂度，并且空间复杂度优于快排的O(logn)，但是依然是不稳定的排序。 |
7. 归并排序
代码实现，注意，归并排序的特性可以在单链表中实现O(nlongn)时间复杂度的排序~
/**
* 合并两个有序数组
* @param array $arr
* @param $low
* @param $mid
* @param $high
* @return array
*/
function merge_div_array(array &$arr, $low, $mid, $high) {
$tmpArr = [];
$i = $low;
$j = $mid + 1;
$tmpIdx = 0;
while ($i <= $mid && $j <= $high) {
if ($arr[$i] <= $arr[$j]) {
$tmpArr[$tmpIdx++] = $arr[$i++];
} else {
$tmpArr[$tmpIdx++] = $arr[$j++];
}
}
// 处理剩余的数组
while ($i <= $mid) {
$tmpArr[$tmpIdx++] = $arr[$i++];
}
while ($j <= $high) {
$tmpArr[$tmpIdx++] = $arr[$j++];
}
foreach ($tmpArr as $idx => $val) {
// 这里要注意是 $idx + $low
$arr[$idx + $low] = $val;
}
return;
}
/**
* 归并数组的辅助函数：分治，然后合并组装
* @param array $arr
* @param $low
* @param $high
*/
function sort_merge_proxy(array &$arr, $low, $high) {
$mid = intval(($low + $high) / 2);
if ($low < $high) {
$this->sort_merge_proxy($arr, $low, $mid);
$this->sort_merge_proxy($arr, $mid + 1, $high);
$this->merge_div_array($arr, $low, $mid, $high);
}
return;
}
/**
* 归并排序，该特性甚至可以在单链表中排序实现 O(nLogn)的时间复杂度排序
* @param array $arr
* @return array
*/
function merge_sort(array $arr) {
$len = count($arr);
if ($len <= 1) {
return $arr;
}
$this->sort_merge_proxy($arr, 0, $len - 1);
return $arr;
}
8. OK，我们来看看一些语言中的排序库函数如何实现的
8.1 PHP的sort函数如何实现
参考： https://tyloafer.github.io/posts/30174/
白话描述：
1、如果容量<=16, 使用插入排序;
2、如果容量>16，使用快速排序，快速排序使用迭代的形式，并且选择pivot有一个根据容量大小进行三数取中、五数取中的策略。
这里算法中用的临界值是16，为什么？“临界值不是计算出来的，算是个经验值，具体对算法性能的影响取决于机器性能，内存大、CPU强的机器当然可以取更大的临界值~”
