排序
基本概念
稳定性：稳定性是指两个相同的值，排序前后的顺序保持不变，即该排序算法是稳定的
衡量标准：时间复杂度、空间复杂度
内部排序
插入排序：直接插入排序、折半插入排序、希尔排序
交换排序：冒泡排序、快速排序
选择排序：简单选择排序、堆排序
归并排序
基数排序
外部排序
多路归并排序
注：基于比较的排序，至少进行比较次数为 log2(n!) 【向上取整】
一趟排序能确定一个元素最终位置的排序算法有：简单选择排序、快速排序、堆排序、冒泡排序
趟次数与初始状态无关的排序算法：插入排序、选择排序、基数排序
简单选择排序的关键字比较次数与待排序元素序列的初始排列无关
| 算法 | 最好情况 | 平均情况 | 最坏情况 | 空间复杂度 | 是否稳定 |
| 直接插入排序 | O(n) |
O( |
O( ) |
O(1) | 是 |
| 冒泡排序 | O(n) | O() |
O() |
O(1) | 是 |
| 简单选择排序 | O() |
O() |
O() |
O(1) | 否 |
| 希尔排序 | O(1) | 否 | |||
| 快速排序 | O(nlog2(n)) | O(nlog2(n)) | O() |
O(log2(n)) | 否 |
| 堆排序 | O(nlog2(n)) | O(nlog2(n)) | O(nlog2(n)) | O(1) | 否 |
| 2-路归并排序 | O(nlog2(n)) | O(nlog2(n)) | O(nlog2(n)) | O(n) | 是 |
| 基数排序 | O(d(n+r)) | O(d(n+r)) | O(d(n+r)) | O(r) | 是 |
附：
既然有排序算法，是否有乱序算法
PHP:
<?php $arr = []; for($i = 0; $i < 100; $i++) { $arr[$i] = $i+1; } for($i = 0; $i < 100; $i++) { $rand = rand(0,99); $temp = $arr[$i]; $arr[$i] = $arr[$rand]; $arr[$rand] = $temp; }
原创文章，作者：奋斗，如若转载，请注明出处：https://blog.ytso.com/tech/pnotes/20715.html