常见排序算法比较
参考资料：各种排序算法比较
参考资料：快速排序算法
必须知道的八大种排序算法【java实现】（一） 冒泡排序、快速排序 （这篇文章中存在部分错误，但是代码示例较为完备，可以当着示例来看）
算法复杂度和算法稳定性的理解
时间复杂度：元素进行比较和移动的次数；
空间复杂度：算法执行过程中，需要的辅助内存情况；
算法稳定性：对于同值元素位置的改变情况决定，如果不改变，则属于稳定性好的算法，否则为不稳定的算法。
对冒泡排序算法最好情况下时间复杂度为O(n)的理解，及时间复杂度的具体算法：冒泡排序最佳情况的时间复杂度，为什么是O(n)
下面是冒泡排序算法的示例：
示例代码
参考git仓库：
关键点
各种排序算法在：时间算法复杂度、空间复杂度、算法稳定性、算法难易度上各有所长，需要根据场景来定；比如对大部分有序的场景，采用插入排序/冒泡排序算法；对于数据量大时，对时间敏感的情况下，使用归并排序/快排算法合适；对于对内存敏感的场景，则不宜选用归并排序/快排算法，可采用shell排序。
归并排序算法时间复杂度上稳定，为O（nlog2n），但是空间复杂度较高，通常为O(n)；如果希望降低空间复杂度可以，采用原地归并算法，可以将空间复杂度降低至O(nlogn),但是会损坏时间复杂度，所以需要在时间复杂度和空间复杂度上进行折中，根据具体应用场景选择；
快排算法，不稳定，平均时间复杂度为O（nlog2n），空间复杂度为O(log2n) ~ O(n)，当数据量大时优势明显；当数据量小时，通常采用插入排序算法。
jdk中的ArrayList.sort（）方法
jdk1.6及其以前，使用归并排序算法；
jdk1.7、1.8 默认情况下使用TimSort，除非用户显式指定使用老式的归并排序算法LegacyMergeSort时。
TimSort 综合使用二分查找插入算法和归并排序算法，以求性能上达到最佳。代码分析参考：TimSort in Java 7
jdk中的sort方法体现了如下思路：
1、依据待排序数组的情况，选择不同的排序算法；比如：当待排序数组的大小小于设定值32时，则直接使用二分查找插入算法，否则使用真正的TimSort排序。
2、TimSort排序的高明之处在于：特殊处理已排序的数组内容，减小算法复杂度；分块处理待排序数组，确保每个元素最多移动的次数，不至于因为数组大小N增大，算法复杂度越来越大；对块进行归并处理。
jdk中的Arrays.sort（）方法
采用DualPivotQuicksort 双轴快速排序算法。算法步骤：
1.对于很小的数组（长度小于27），会使用插入排序。
2.选择两个点P1,P2作为轴心，比如我们可以使用第一个元素和最后一个元素。
3.P1必须比P2要小，否则将这两个元素交换，现在将整个数组分为四部分：
（1）第一部分：比P1小的元素。
（2）第二部分：比P1大但是比P2小的元素。
（3）第三部分：比P2大的元素。
（4）第四部分：尚未比较的部分。
在开始比较前，除了轴点，其余元素几乎都在第四部分，直到比较完之后第四部分没有元素。
4.从第四部分选出一个元素a[K]，与两个轴心比较，然后放到第一二三部分中的一个。
5.移动L，K，G指向。
6.重复 4 5 步，直到第四部分没有元素。
7.将P1与第一部分的最后一个元素交换。将P2与第三部分的第一个元素交换。
8.递归的将第一二三部分排序。
