如何分析一个排序算法 算法的执行效率 最好情况，最坏情况，平均情况时间复杂度 时间复杂度的系数，常数，低阶 时间复杂度反应的是数据规模n很大的时候的一个增长趋势 所有它表示的时候会忽略系数，常数，低阶 比较次数和交换(或移动次数) 算法的内存消耗 空间复杂度 原地排序(Sorted in place) 特指空间复杂度是O(1)的排序算法 算法的稳定性 待排序的序列中存在值相等的元素，经过排序后，相等元素之间原有的先后顺序不变 有序度 有序度是数组中具有有序关系的元素对的个数 数学表达式：有序元素对：a[i] <= a[j], 如果 i < j 例子 一个数据. 2, 4, 3, 1, 5, 6 这组数据的有序度为11， 因其有序元素对为11 个 (2, 4), (2, 3), (2, 5), (2, 6) (4, 5), (4, 5), (3, 5), (3, 6) (1, 5), (1, 6), (5, 6) 满有序度 同理，对于一个倒序排列的数组，比如 6, 5, 4, 3, 2, 1 有序度为0 对于一个完全有序的数组，比如1, 2, 3, 4, 5, 6 有序度就是 (n * (n - 1)) / 2， 就是15 逆序度 逆序度的定义正好跟有序度相反(默认从小到大排序) 逆序元素对：a[i] > a[j], 如果 i < j 公式： 逆序对：= 满有序度 - 有序度 链表排序注意点 一般而言，考虑只能改变节点位置，冒泡排序相比于数据实现，比较次数一致，但交换时操作更复杂 插入排序，不需要再有后移操作，找到位置直接插入，但排序完毕后可能需要倒置链表 选择排序比较次数一致，交换操作同样比较麻烦 综上，时间复杂度和空间复杂度并无明显变化，若追求极致性能，冒泡排序的时间复杂度系数会变大，插入排序系统会减小，选择排序无明显变化 排序算法 冒泡排序 插入排序 选择排序 归并排序 快速排序 桶排序 计数排序 基数排序 其他 PHP排序算法 各排序算法时间复杂度比较 参考资料 一次性弄懂到底什么叫做分治思想 快速排序算法分析和实现