快速排序和归并排序是排序算法中应用比较广泛的两个算法，其时间复杂度均为 O(N*logN), 对于空间复杂度，前者为 O(1) ， 后者则为 O(N), 因为综合而言，快速排序应用更加广泛。本篇经验就分享一下 Java 中如何实现快速排序和归并排序，以及他们和普通排序算法的性能比较。注意：快速排序是不稳定排序，而归并排序是稳定排序，在某些特殊业务场景下，后者可能是更好的选择。
工具/原料
1
Eclipse
2
JDK1.8
方法/步骤
1
快速排序：主体框架代码图示：快速排序是分治算法的经典应用，其先将数组分区（分区函数），获取一个分界点（此点已处于正确顺序处），然后再分别对前后两个子数组进行快速排序。
2
快速排序：分区函数图示：框架代码中调用的分区函数，选定数组待排序区域的最后一个元素，遍历并移动剩余元素，获取分界点，将选定元素和分界点元素交换位置即可。
3
归并排序：主体框架代码图示：归并排序同样是分治算法思想的应用，框架代码的含义就是将较大数组分为两个小数组，排序后，调用合并函数合并到一起即可。
4
归并排序：合并函数图示：就是将数组已排序的两个部分合并为一个整体有序的部分，这里无法做到原地排序，需要创建一个临时数组（ 这也是归并排序空间复杂度为O(n)的原因 ），分别遍历有序部分，填充临时数组，然后将临时数组拷贝到原始区域。
5
实现插入排序图示：插入排序是一个简单的排序算法，其时间复杂度为 O(n²)，通过嵌套循环完成排序。这里主要用于后续的性能测试。
6
编写测试代码图1示：构建数据，创建1000个数量为1000的随机整数数组，并复制3份，通过相同数据，分别测试3个排序算法的性能。图2示：主方法中，先获取数据，然后分别调用3个算法对数据排序，统计执行时间。
7
测试结果图示：测试10次，分别计算3种排序算法的耗时平均值，可以明显看出，快速排序耗时最少，归并排序次之，插入排序最多，和算法的时间复杂度吻合。
上一篇：excel要怎样排序
下一篇：excel中如何排序。