文章目录
思考前言如何分析一个排序算法？排序算法的执行效率排序算法的内存消耗排序算法的稳定性
如何选择合适的排序算法？如何优化快速排序？解答思考题参考链接
思考
为什么插入排序比冒泡排序更受欢迎？如何用快排思想在O(n)内查找第K大元素？如何根据年龄给100万用户数据排序？（线性排序）如何实现一个通用的、高性能的排序函数？（排序优化）
前言
我最近在系统整理一些 Java 后台方面的面试题和参考答案，有找工作需求的童鞋，欢迎关注我的 Github 仓库，如果觉得不错可以点个 star 关注 ：
1、awesome-java-interview2、awesome-java-notes
如何分析一个排序算法？
是否原地排序是否稳定最好、最坏、平均时间复杂度空间复杂度是否基于比较冒泡排序是是O(n)、 O(n^2)、 O(n^2)O(1)是插入排序是是O(n)、 O(n^2)、 O(n^2)O(1)是选择排序是否O(n^2)、 O(n2)、O(n2)O(1)是希尔排序是否O(n)、O(n2)、O(n1.3)O(1)是快速排序是否O(nlogn)、O(n^2)、O(nlogn)O(logn)~O(n)是归并排序否是O(nlogn)、O(nlogn)、O(nlogn)O(n)是计数排序否是O(n+k)、O(n+k)、O(n+k)，k 是数据范围O(n+k)否桶排序否是O(n)、O(n)、O(n)O(N+M)，N表示待排数据个数，M表示桶个数否基数排序否是O(nk)、O(nk)、O(n*k)，k 是维度O(n+k)否堆排序是否O(nlogn)、O(nlogn)、O(nlogn)O(1)是
排序算法的执行效率
1、最好情况、最坏情况、平均情况时间复杂度2、时间复杂度的系数、常数 、低阶
时间复杂度反映数据规模 n 很大时的一个增长趋势，常忽略系数、常数、低阶实际软件开发中，数据规模可能比较小，比较同一阶时间复杂度的排序算法时，不能忽略系数、常数、低阶 3、比较次数和交换（或移动）次数
基于比较的算法会涉及两种操作：元素比较大小、元素交换或移动分析排序算法执行效率时，应该要考虑比较次数（或移动）次数
排序算法的内存消耗
原地排序（Sorted in place）：特指空间复杂度为 O(1) 的排序算法算法的内存消耗可以通过空间复杂度来衡量
排序算法的稳定性
稳定的排序算法： 指待排序的序列中存在值相等的元素时，经过排序后，相等元素之间原有的先后顺序不变
如何选择合适的排序算法？
对小规模数据进行排序，可以选择时间复杂度是 O(n^2) 的算法对大规模数据进行排序，时间复杂度是 O(nlogn) 的算法更加高效为了兼顾任意规模数据的排序，一般都会首选时间复杂度是 O(nlogn) 的排序算法来实现排序函数
如何优化快速排序？
快速排序出现 O(n^2)时间复杂度的主要原因是因为分区节点选择不够合理最理想的分区节点是：被分区点分开的两个分区中，数据的数量差不多方法
1、三数取中法（五数取中、十数取中等）：从区间的首、尾、中间，分别取出一个数，然后对比大小，取这 3 个数的中间值作为分区点2、随机法：每次从要排序的区间中，随机选择一个元素作为分区点3、等等
解答思考题
1. 为什么插入排序比冒泡排序更受欢迎？
从代码实现上来看，冒泡排序的数据交换要比插入排序的数据移动要复杂，冒泡排序需要 3 个赋值操作，而插入排序只需要 1 个。
// 冒泡排序中数据的交换操作：
if (a[j] > a[j+1]) { // 交换
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
flag = true;
}
// 插入排序中数据的移动操作：
if (a[j] > value) {
a[j+1] = a[j]; // 数据移动
} else {
break;
}
2. 如何用快排思想在O(n)内查找第K大元素？
比如，4， 2， 5， 12， 3 这样一组数据，第 3 大元素就是 4。 我们选择数组区间 A[0…n-1] 的最后一个元素 A[n-1] 作为 pivot，对数组 A[0…n-1] 原地分区，这样数组就分成了三部分，A[0…p-1]、A[p]、A[p+1…n-1]。 如果 p+1=K，那 A[p] 就是要求解的元素；如果 K>p+1, 说明第 K 大元素出现在 A[p+1…n-1] 区间，我们再按照上面的思路递归地在 A[p+1…n-1] 这个区间内查找。同理，如果 K 3. 如何根据年龄给100万用户数据排序？（线性排序） 假设年龄的范围最小 1 岁，最大不超过 120 岁。可以遍历这 100 万用户，根据年龄将其划分到这 120 个桶里，然后依次顺序遍历这 120 个桶中的元素。这样就得到了按照年龄排序的 100 万用户数据。 4. 如何实现一个通用的、高性能的排序函数？（排序优化） 1.数据量不大时，可以采取用时间换空间的思路 2.数据量大时，优化快排分区点的选择 3.防止堆栈溢出，可以选择在堆上手动模拟调用栈解决 4.在排序区间中，当元素个数小于某个常数是，可以考虑使用O(n^2)级别的插入排序 5.用哨兵简化代码，每次排序都减少一次判断，尽可能把性能优化到极致 参考链接 《数据结构与算法之美》专栏 王争