说明
排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。 常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序（不讨论细节）、计数等。
通用测试数据
public abstract class Constant<T extends Number> {
public static final Integer[] array = new Integer[]{8, 34, 64, 51, 33, 22, 44, 55, 88, 1, 0, 2, 2};
// 有序数组
static final Integer[] array2 = new Integer[]{0, 1, 2, 2, 8, 22, 33, 34, 44, 51, 55, 64, 88};
public static final int len = array.length;
public final void printResult(T[] array) throws Exception {
if (array == null || array.length == 0)
throw new Exception("no element or invalid element in array");
// java 8 lambda
System.out.println(
Arrays.stream(array)
.map(Object::toString)
.collect(Collectors.joining(",", "[", "]")));
}
/**
* 原始版
*
* @param array
* @param len
* @return T[]
*/
public abstract void sort(T[] array, int len) throws Exception;
/**
* 优化版
*
* @param array
* @param len
* @return T[]
*/
public void sort2(T[] array, int len) throws Exception {
}
}
插入排序
插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
插入排序示意图
算法步骤：
- 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
- 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
public class InsertionSort extends Constant<Integer> {
public static void main(String[] args) throws Exception {
new InsertionSort().sort(Constant.array, Constant.len);
}
@Override
public void sort(Integer[] array, int len) throws Exception {
int j, p;
int temp;
for (p = 1; p < len; p++) { // 外层循环固定是len-1趟
temp = array[p];
for (j = p; j > 0 && temp < array[j - 1]; j--) {
array[j] = array[j - 1]; // j后移，j--
}
array[j] = temp; // 找到位置，插入
}
super.printResult(array);
}
}
希尔排序
也称递减增量排序算法，是插入排序的一种更高效的改进版本。 先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
希尔排序示意图
算法步骤：
- 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
- 按增量序列个数k，对序列进行k 趟排序；
- 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
public class ShellSort extends Constant<Integer> {
public static void main(String[] args) throws Exception {
new ShellSort().sort(Constant.array, Constant.len);
}
@Override
public void sort(Integer[] array, int len) throws Exception {
int i, j, increment;
int temp;
// 使用一种流行但不好的序列h=[h/2]下取整
for (increment = len / 2; increment > 0; increment /= 2) {
for (i = increment; i < len; i++) {
temp = array[i];
for (j = i; j >= increment; j -= increment) {
if (temp < array[j - increment]) array[j] = array[j - increment];
else break;
}
array[j] = temp;
}
}
super.printResult(array);
}
}
选择排序
选择排序（Selection sort）也是一种简单直观的排序算法。其思想是每次选取最大（最小）的元素放到排序序列的起始位置
选择排序示意图
算法步骤：
- 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
- 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
- 重复第二步，直到所有元素均排序完毕。
public class SelectSort extends Constant<Integer> {
public static void main(String[] args) throws Exception {
new SelectSort().sort(Constant.array, Constant.len);
}
@Override
public void sort(Integer[] array, int len) throws Exception {
select(array, len);
super.printResult(array);
}
private void select(Integer[] a, int length) {
if (a == null || length <= 0) {
return;
}
int minary; // 定义一个最小坐标
int temp; // 定义一个临时变量
for (int i = 0; i < length - 1; i++) {
minary = i; // 将最小下标附一个初始值
for (int j = i + 1; j < length; j++) { // 遍历无序区 的元素
if (a[j] < a[minary]) {
minary = j;
}
}
if (minary != i) {
temp = a[i];
a[i] = a[minary];
a[minary] = temp;
}
}
}
}
冒泡排序
冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。 走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
冒泡排序示意图
算法步骤：
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
public class BubbleSort extends Constant<Integer> {
private static long time = 0L;
private static long time2 = 0L;
public static void main(String[] args) throws Exception {
new BubbleSort().sort(array2, len); // array:13474,array2:12832 相差明显
new BubbleSort().sort2(array2, len); // array:1284,array2:1283
System.out.println("没有优化：" + time);
System.out.println("优化：" + time2);
}
/**
* 原始版
*/
@Override
public void sort(Integer[] array, int len) throws Exception {
long t = System.nanoTime();
for (int i = 0; i < array.length - 1; i++) { // 外层循环控制排序趟数
for (int j = 0; j < array.length - 1 - i; j++) { // 内层循环控制每一趟排序多少次
if (array[j] > array[j + 1]) {
Integer temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
time = System.nanoTime() - t;
super.printResult(array);
}
/**
* 优化版
*/
@Override
public void sort2(Integer[] array, int len) throws Exception {
long t = System.nanoTime();
boolean flag;
for (int i = 0; i < array.length; i++) {
flag = true;
// 思路是每次进下一趟冒泡的时候给flag设置true,如果被修改说明还有元素没有被排序，继续重复操作
// 如果经过一趟下来，没有元素被交换【没有设置flag=false】,此时说明元素全部有序，直接退出
for (int j = 0; j < array.length - 1 - i; j++) {
if (array[j] > array[j + 1]) {
Integer temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
flag = false;
}
}
if (flag) {
break;
}
}
time2 = System.nanoTime() - t;
super.printResult(array);
}
}
归并排序
归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
归并排序示意图
算法步骤：
- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置
- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
- 重复步骤3直到某一指针达到序列尾
- 将另一序列剩下的所有元素直接复制到合并序列尾
public class MergeSort extends Constant<Integer> {
public static void main(String[] args) throws Exception {
new MergeSort().sort(Constant.array, Constant.len);
}
@Override
public void sort(Integer[] array, int len) throws Exception {
Integer[] t = new Integer[len];
mSort(array, t, 0, len - 1);
super.printResult(array);
}
private void mSort(Integer[] arr, Integer[] temp, int left, int right) {
int center;
if (left < right) {
center = (left + right) / 2;
// 对前半部分进行排序
mSort(arr, temp, left, center);
// 对后半部分进行排序
mSort(arr, temp, center + 1, right);
// 合并
// leftPos左半边的开始
// rightPos右半边的开始
merge(arr, temp, left, center + 1, right);
}
}
private void merge(Integer[] arr, Integer[] tempArray, int leftPos, int rightPos, int rightEnd) {
int i, leftEnd, numElements, tempPos;
leftEnd = rightPos - 1;
tempPos = leftPos;
numElements = rightEnd - leftPos + 1;
// 主循环
while (leftPos <= leftEnd && rightPos <= rightEnd)
if (arr[leftPos] <= arr[rightPos]) tempArray[tempPos++] = arr[leftPos++];
else tempArray[tempPos++] = arr[rightPos++];
// 复制第一个数组的剩余数据
while (leftPos <= leftEnd) tempArray[tempPos++] = arr[leftPos++];
// 复制第二个数组的剩余数据
while (rightPos <= rightEnd) tempArray[tempPos++] = arr[rightPos++];
// 把临时数组拷贝回来
for (i = 0; i < numElements; i++, rightEnd--) {
arr[rightEnd] = tempArray[rightEnd];
}
}
}
快速排序
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。 快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。
快速排序示意图
算法步骤：
- 从数列中挑出一个元素，称为 “基准”（pivot），
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。 递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
public class QuickSort extends Constant<Integer> {
public static void main(String[] args) throws Exception {
new QuickSort().sort(array, len);
}
@Override
public void sort(Integer[] array, int len) throws Exception {
quick(array, 0, len - 1);
super.printResult(array);
}
private void quick(Integer[] list, int low, int high) {
if (low < high) {
int middle = QuickSort.quickSortBy3Integers(list, low, high); // 三数中值分割法
// int middle = quickSort(list, low, high); // 将list数组进行一分为二
quick(list, low, middle - 1); // 对低字表进行递归排序
quick(list, middle + 1, high); // 对高字表进行递归排序
// 快速选择排序，这里需要if判断一下，少一次递归
}
}
// 一般方法
public int quickSort(Integer[] list, int low, int high) {
int tmp = list[low]; // 数组的第一个作为中轴
while (low < high) {
while (low < high && list[high] >= tmp) {
high--;
}
list[low] = list[high]; // 比中轴小的记录移到低端
while (low < high && list[low] <= tmp) {
low++;
}
list[high] = list[low]; // 比中轴大的记录移到高端
}
list[low] = tmp; // 中轴记录到尾
return low;
}
// 使用三数中值
private static int quickSortBy3Integers(Integer[] array, int low, int high) {
// 三数取中
int mid = low + (high - low) / 2;
if (array[mid] > array[high]) {
swap(array[mid], array[high]);
}
if (array[low] > array[high]) {
swap(array[low], array[high]);
}
if (array[mid] > array[low]) {
swap(array[mid], array[low]);
}
int key = array[low];
while (low < high) {
while (array[high] >= key && high > low) {
high--;
}
array[low] = array[high];
while (array[low] <= key && high > low) {
low++;
}
array[high] = array[low];
}
array[high] = key;
return high;
}
private static void swap(Object a, Object b) {
Object temp = a;
a = b;
b = temp;
}
}
堆排序
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。 堆排序的平均时间复杂度为 Ο(nlogn) 。
堆排序示意图
算法步骤：
- 创建一个堆H[0..n-1]
- 把堆首（最大值）和堆尾互换
- 把堆的尺寸缩小1，并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置
- 重复步骤2，直到堆的尺寸为1
public class HeapSort extends Constant<Integer> {
private static long time = 0L;
private static long time2 = 0L;
public static void main(String[] args) throws Exception {
new HeapSort().sort(Constant.array, Constant.len);
new HeapSort().sort2(Constant.array, Constant.len);
System.out.println("耗费时间：" + time); // array1：48441,array2：46517 几乎相同
System.out.println("优化耗费：" + time2); // array1：23739,array2：27589 几乎相同，比未优化快，但偶尔出现很慢，未知原因
}
/**
* 默认是小根堆
*/
PriorityQueue<Integer> queue = new PriorityQueue<>(11, Integer::compareTo);
/**
* 另外堆排序的比较次数和序列的初始状态有关，但只是在序列初始状态为堆的情况下比较次数显著减少，在序列有序或逆序的情况下比较次数不会发生明显变化。
*/
@Override
public void sort(Integer[] array, int len) {
long t = System.nanoTime();
for (Integer integer : array) {
queue.offer(integer);
}
for (int i = 0; i < array.length; i++) {
array[i] = queue.poll();
}
time = System.nanoTime() - t;
}
@Override
public void sort2(Integer[] array, int n) throws Exception { // 传入数组以及数组的大小
long t = System.nanoTime();
for (int i = (n - 2) / 2; i >= 0; i--) { // 对数组进行heapfiy产生最大值array[0]
__shiftdown(array, n, i); // shiftdown所有可以下沉的父节点
}
for (int j = n - 1; j > 0; j--) {
// 把每次产生的最大值调到数组的后面去
int temp = array[0];
array[0] = array[j];
array[j] = temp;
__shiftdown(array, j, 0);
}
time2 = System.nanoTime() - t;
super.printResult(array);
}
private void __shiftdown(Integer[] arr, int n, int k) { // 下沉操作，传入数组以及需要排序的个数和下沉的索引
int e = arr[k]; // 记录首个下沉的节点的值
while (2 * k + 1 <= n - 1) { // 保证需要进行操作的节点至少有左孩子
int maxindex = 2 * k + 1; // 假设最大的子节点为左孩子
if (2 * k + 2 <= n - 1
&& arr[2 * k + 2] > (int) arr[maxindex]) { // 如果存在右孩子并且右孩子比左孩子大
maxindex = 2 * k + 2; // 最大的子节点指向右孩子
}
if (e < arr[maxindex]) { // 下沉节点的值要小于他的孩子节点
arr[k] = arr[maxindex]; // 下沉节点的值被大孩子的值替换
k = maxindex; // 更新需要下沉节点的索引
} else break;
}
arr[k] = e; // 最后不能下沉的节点赋值为首下沉节点的值
}
}
桶排序
算法思想：是将阵列分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的阵列内的数值是均匀分配的时候，桶排序使用线性时间 O(n)。但桶排序并不是比较排序，他不受到 O(nlogn) 下限的影响。 简单来说，就是把数据分组，放在一个个的桶中，然后对每个桶里面的在进行排序。
例如要对大小为[1..1000]范围内的n个整数A[1..n]排序
首先，可以把桶设为大小为10的范围，具体而言，设集合B[1]存储[1..10]的整数，集合B[2]存储(10..20]的整数，……集合B[i]存储((i-1)10, i10]的整数，i = 1,2,..100。总共有100个桶。
然后，对A[1..n]从头到尾扫描一遍，把每个A[i]放入对应的桶B[j]中。再对这100个桶中每个桶里的数字排序，这时可用冒泡，选择，乃至快排，一般来说任何排序法都可以。
最后，依次输出每个桶里面的数字，且每个桶中的数字从小到大输出，这样就得到所有数字排好序的一个序列了。
假设有n个数字，有m个桶，如果数字是平均分布的，则每个桶里面平均有n/m个数字。如果
对每个桶中的数字采用快速排序，那么整个算法的复杂度是
O(n + m * n / m * log(n / m)) = O(n + nlogn – nlogm)
从上式看出，当m接近n的时候，桶排序复杂度接近O(n)
当然，以上复杂度的计算是基于输入的n个数字是平均分布这个假设的。这个假设是很强的 ，实际应用中效果并没有这么好。如果所有的数字都落在同一个桶中，那就退化成一般的排序了。
前面说的几大排序算法 ，大部分时间复杂度都是 O(n2)，也有部分排序算法时间复杂度是 O(nlogn)。而桶式排序却能实现 O(n) 的时间复杂度。但桶排序的缺点是：
1）首先是空间复杂度比较高，需要的额外开销大。排序有两个数组的空间开销，一个存放待排序数组，一个就是所谓的桶，比如待排序值是从0到m-1，那就需要m个桶，这个桶数组就要至少m个空间。
2）其次待排序的元素都要在一定的范围内等等。
桶排序
public class BucketSort extends Constant<Integer> {
public static void main(String[] args) throws Exception {
new BucketSort().sort(array, len);
}
@Override
public void sort(Integer[] array, int len) throws Exception {
bucketSort(array);
}
private void bucketSort(Integer[] arr) throws Exception {
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for (Integer item : arr) {
max = Math.max(max, item);
min = Math.min(min, item);
}
// 桶数
int bucketNum = (max - min) / arr.length + 1;
ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
for (int i = 0; i < bucketNum; i++) {
bucketArr.add(new ArrayList<>());
}
// 将每个元素放入桶
for (Integer value : arr) {
int num = (value - (Integer) min) / (arr.length);
bucketArr.get(num).add(value);
}
// 对每个桶进行排序
for (ArrayList<Integer> integers : bucketArr) {
Collections.sort(integers);
}
int i = 0;
for (ArrayList<Integer> arrayList : bucketArr) {
for (Integer integer : arrayList) {
arr[i++] = integer;
if (i == arr.length - 1) break;
}
}
System.out.println("使用toString()方法：" + bucketArr.toString());
super.printResult(arr);
}
}
计数排序
计数排序的核心思想是，构建一个足够大的数组，数组大小需要保证能够把所有元素都包含在这个数组上。当元素非常大时就不适用了。
public class CountSort extends Constant<Integer> {
private static long time = 0L;
public static void main(String[] args) throws Exception {
new CountSort().sort(Constant.array2, Constant.len);
System.out.println("耗费时间：" + time); // array1：18606,array2：18927 几乎相同
}
@Override
public void sort(Integer[] array, int len) throws Exception {
countSort(array);
}
private void countSort(Integer[] arr) throws Exception {
long t = System.nanoTime();
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
// 找出数组中的最大最小值
for (Integer value : arr) {
max = Math.max(max, value);
min = Math.min(min, value);
}
// 比max大1
int[] help = new int[max - min + 1];
// 找出每个数字出现的次数
for (Integer integer : arr) {
int mapPos = integer - min;
help[mapPos]++;
}
int index = 0;
for (int i = 0; i < help.length; i++) {
// 因为可能有重复的数据，所以需要循环
while (help[i]-- > 0) {
arr[index++] = i + min;
}
}
time = System.nanoTime() - t;
super.printResult(arr);
}
}
基数排序
基数排序用于对多关键字域数据进行排序，每次对数据按一种关键字域进行排序，然后将该轮排序结果按该关键字的大小顺序堆放，依次进行其他关键字域的排序，最后实现序列的整体排序。
对于整数，我们可以将个位、十位、百分位等依次作为关键字排序。
其中，d 为位数，r 为基数，n 为原数组个数。 在基数排序中，因为没有比较操作，所以在复杂上，最好的情况与最坏的情况在时间上是一致的，均为 O(d * (n + r))。
public class RadixSort extends Constant<Integer> {
public static void main(String[] args) throws Exception {
new RadixSort().sort(Constant.array, Constant.len);
}
@Override
public void sort(Integer[] array, int len) throws Exception {
int max = array[0];
// 计算数组中的最大值
for (int i = 1; i < array.length; i++) {
if (array[i] > max) {
max = array[i];
}
}
// 基数1，10，100，1000，...
int bit = 1;
while (max / bit > 0) {
radix(array, bit);
bit *= 10;
}
super.printResult(array);
}
private void radix(Integer[] array, int bit) {
// 临时数组存储所有元素
Integer[] temp = new Integer[array.length];
// 0~9十个桶，每个桶存放的是计算出来的该位上数的个数
int[] bucket = new int[10];
for (Integer integer : array) {
bucket[(integer / bit) % 10]++;
}
// 再次遍历这个桶数组，将桶里数的个数变为 前面桶的个数加上自己桶里的个数 (bucket[i] += bucket[i-1]) 这一步完成之后
// 我们就可以从桶里知道对应数排序后的位置
for (int i = 1; i < bucket.length; i++) {
bucket[i] += bucket[i - 1];
}
// 从后面开始排序
for (int i = array.length - 1; i >= 0; i--) {
// 根据该数对应位上的数字找到对应的桶从而得到桶里的数字
// 计数=索引值+1
int index = (array[i] / bit) % 10;
temp[bucket[index] - 1] = array[i];
bucket[index]--;
}
// 每次根据一位进行排序，都需要拷贝回原数组
System.arraycopy(temp, 0, array, 0, temp.length);
}
}
排序算法比较
外排序
常见的外排序算法 - 多路归并
外排序算法的核心思路在于把文件分块读到内存，在内存中对每块文件依次进行排序，最后合并排序后的各块数据，依次按顺序写回文件。外排序需要进行多次磁盘读写，因此执行效率往往低于内排序，时间主要花费于磁盘读写上。我们给出外排序的算法步骤如下： 假设文件需要分成k块读入，需要从小到大进行排序。
- 依次读入每个文件块，在内存中对当前文件块进行排序（应用恰当的内排序算法）。此时，每块文件相当于一个由小到大排列的有序队列。
- 在内存中建立一个最小值堆，读入每块文件的队列头。
- 弹出堆顶元素，如果元素来自第i块，则从第i块文件中补充一个元素到最小值堆。弹出的元素暂存至临时数组。
- 当临时数组存满时，将数组写至磁盘，并清空数组内容。
- 重复过程3、4，直至所有文件块读取完毕。
常见问题
排序算法的下界和上界
1、基于比较的排序算法的最优下界为什么是 O(nlogn) ？
可以使用决策二叉树证明
比较排序可以构造决策树，根节点代表原始序列a1,a2,a3……an，所有叶子节点都是这个序列的重排（共有n!个，其中有一个就是我们排序的结果a1’,a2’,a3’……an’）。 如果每次比较的结果都是等概率的话（恰好划分为概率空间相等的两个事件），那么二叉树就是高度平衡的，深度至少是 log(n!)。 又因为 log(n!) 的增长速度与 nlogn 相同,即 log(n!)= O(nlogn)，这就是通用排序算法的最低时间复杂度 O(nlogn) 的依据。
2、假设A[1…n]是一个有n个不同数的数组。若i>j且A[i]<A[j]，则对偶（i，j）称为A的一个逆序对（inversion）
基于比较的排序的每次交换位置涉及一对逆序对，总共交换的次数就是逆序对的数量。即运行时间为：O(n+d)O(n+d)，n为数组大小，d为逆序对数目，一个n个元素的数组中逆序对数目最多为 n(n−1)/2个。 排序需要耗费的时间最少是逆序对的个数，但是对于不是基于比较的排序则不成立，比如基数，桶排序等。
Collections.sort使用哪种排序算法 ？Arrays.sort() ？
1、Arrays.sort()
底层调用DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0)，翻译过来就是双轴快速排序。
数组的长度小于QUICKSORT_THRESHOLD（286），使用双轴快速排序 数组长度小于INSERTION_SORT_THRESHOLD（值为47）的话，使用插入排序。 那如果大于286，它就会检测数组的连续升序和连续降序性好不好，如果好的话就用归并排序，不好的话就用快速排序
总结一下Arrays.sort()方法，如果数组长度大于等于286且连续性好的话，就用归并排序，如果大于等于286且连续性不好的话就用双轴快速排序。 如果长度小于286且大于等于47的话就用双轴快速排序，如果长度小于47的话就用插入排序。
但是，当数组的元素是对象时，则与Collections.sort()相同，内部使用legacyMergeSort()和TimSort.sort()。
2、Collections.sort()
底层调用归并排序legacyMergeSort()和TimSort.sort()，实际就是用了Arrays.sort。
Timsort是结合了归并排序（merge sort）和插入排序（insertion sort）而得出的排序算法，它在现实中有很好的效率。 大体是说，Timsort是稳定的算法，当待排序的数组中已经有排序好的数，它的时间复杂度会小于 nlogn。与其他合并排序一样，TimSort是稳定的排序算法，最坏时间复杂度是 O(nlogn)。 在最坏情况下，和TimSort算法需要的临时空间是 n/2，在最好情况下，它只需要一个很小的临时存储空间
256M的内存如何对16g的数组进行排序 ？
多路归并，因为没要求存储，只要求了内存，可以多路归并。
具体描述：采用外部排序，先将16g数组分成256M一组（得出64个小数组），然后分别读入内存进行内部排序「比如说可以使用快排」， 将这些组内元素全部排好序之后（需要利用外存），然后运用败者树和置换-选择排序，进行多路归并即可。
海量数据求最大的K个数问题，如何解决 ？
- 按位划分区域，可以尽快的缩小范围，比如最高位 0分一堆，1分成一堆而且不用排序，这是第一选择。
- 最经典的方法当然是堆了，比如要求前1000个最大的数，那就直接建一个1000大小的小根堆，然后遍历，只要发现后面的数比小根堆的根节点大，就把根节点和该数交换，重新调整堆，遍历完之后，堆中的数自然就是最大的1000个数了；
- 当然能使用堆排序的前提是内存中要能够放得下这个K，如果放不下呢？那就只能外部排序了，排序完之后拿到第K大的数即可，当然排序前可以和方法一搭配一下。
海量数据求中位数，如何解决 ？
- 可以按照位来分组，比如说最高位是0的一组，是1的一组，这样可以统计出那一组更少，这样就排除了一大半，然后继续这样排查，最终缩小范围后直接内部排序。
- 直接外部排序，然后取中间值，最笨的方法。
如何在海量数据中找出出现频率最高的前k个数 ？
- 如果重复率很高，可以采用前缀树，因为trie树适用于数据量大，重复多，但是数据种类小必须得可以放入内存；
- 按照hash进行分组，这样就能避免相同的数分到不同区域去了，导致不好统计。hash分组完毕后，然后用前缀树或者hashmap来计算每个组的前k个频率最高的数，最后对各个组的前k个数进行统计即可。
在40亿个乱序且不重复的unsigned int的整数中判断数x是否存在 ？
这里我们把40亿个数中的每一个用32位的二进制来表示，假设这40亿个数开始放在一个文件中。
然后将这40亿个数分成两类:
- 最高位为0
- 最高位为1
并将这两类分别写入到两个文件中，其中一个文件中数的个数<=20亿，而另一个>=20亿（这相当于折半了）；与要查找的数的最高位比较并接着进入相应的文件再查找
再然后把这个文件为又分成两类:
- 次最高位为0
- 次最高位为1
并将这两类分别写入到两个文件中，其中一个文件中数的个数 <=10 亿，而另一个 >= 10亿（这相当于折半了）；与要查找的数的次最高位比较并接着进入相应的文件再查找。 以此类推，就可以找到了，而且时间复杂度为 O(logn)。
海量数据求TopK的普遍方法
- 最快的不需要排序就能排除一大堆的数据的方法就是看“位”，比如最高位为0的分一块，为1的分一块，这样迅速就分出一大块不需要的了，尤其适合找中位数，等分的差不多了就可以进行内部排序了。
- 堆排序，适用于求海量数据最大K或最小K个数；
- 分治hash，适用于那些内存很小，数据很大，但是又想求最大的K个众数的问题，可以先hash到很多个组，然后在组内部使用hashmap或者前缀树，取到组内前K个众数，最后进行组间比较；
- 当然不能忘了万能法，那就是外部排序，然后再进行相应的处理。
以上的gif图片来自博客园
文档信息
- 本文作者：梦境迷离
- 本文链接：https://blog.dreamylost.cn/%E7%AE%97%E6%B3%95/%E7%AE%97%E6%B3%95-%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95.html
- 版权声明：自由转载-非商用-非衍生-保持署名（创意共享3.0许可证）