排序-归并排序
基本思想：是指将两个或两个以上的有序表合并成一个新的有序表。
具体步骤：
(1首先将整个表看成是n个有序子表，每个子表的长度为1。
(2)然后两两归并，得到n/2个长度为2的有序子表。
(3)然后再两两归并,直至得到一个长度为n的有序表为止。
平均时间：O(nlogn)
最好情况：O(nlogn)
最坏情况：O(n2)
辅助空间：O(n)
稳定性：稳定
适用场景：n比较大时
代码实现：
public static void mergeSort(int[] list) {
mergeSort(list, 0, list.length - 1);
}
private static void mergeSort(int[] list, int left, int right) {
if (left >= right)
return;
int center = (left + right) / 2;
mergeSort(list, left, center);
mergeSort(list, center + 1, right);
merge(list, left, center, right);
}
private static void merge(int[] list, int left, int center, int right) {
int[] tmpList = new int[list.length];
int mid = center + 1;
int k = left;
int tmp = left;
while (left <= center && mid <= right) {
if (list[left] <= list[mid])
tmpList[k++] = list[left++];
else {
tmpList[k++] = list[mid++];
}
}
while (left <= center) {
tmpList[k++] = list[left++];
}
while (mid <= right) {
tmpList[k++] = list[mid++];
}
// 将临时数组中的数据保存至原数组中
while (tmp <= right) {
list[tmp] = tmpList[tmp++];
}
}