算法思想
利用递归，将原始序列不断两两分块，直到每块剩下一个元素，这个元素肯定是有序的。然后利用递归的原理合并即可
空间复杂度
空间复杂度应该从拆分上面来看，第一次拆分是1块拆成2快，第二次是2块拆成4块，第三次是4块拆成8块…第n次就是2^(n-1)拆成2^(n)块，总和应该是2^0+2^1+2^2…+2^n为O(n)
时间复杂度
O(nlgn)
每层需要合并的总数为n，一共有logn层，故为nlogn
算法实现思想
首先使用类似于后序遍历的方式，将数组不断的分割，最后在进行归并。
归并的过程是：使用三根指针，第一根指向第一个子表首位元素，第二根指向第一个子表末尾元素，最后一根指向第二个子表末尾元素元素。
在确保第一根位置小于第二根，第二根+1小于第三根的情况下，不断比较第一根和第二根的大小并做相应的替换，替换完毕之后2根指针同时++,直到第一根指针到达左侧最末尾或者第二根指针到达第三根指针位置，即可中断。
java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| private static void mergeSort(int[] arr) {
mergeSort(arr, new int[arr.length], 0, arr.length - 1);
}
private static void mergeSort(int[] arr, int[] temp, int left, int right) {
if (left < right) {
int center = (left + right) / 2;
mergeSort(arr, temp, left, center); // 左边
mergeSort(arr, temp, center + 1, right); // 右边
merge(arr, temp, left, center + 1, right); // 合并两个有序 ett
}
}
private static void merge(int[] arr, int[] temp, int leftPos, int rightPos, int rightEnd) {
int leftEnd = rightPos - 1; // 左边结束下标
int tempPos = leftPos; // 从左边开始算
int numEle = rightEnd - leftPos + 1; // 元素个数
while (leftPos <= leftEnd && rightPos <= rightEnd) {
if (arr[leftPos] <= arr[rightPos])
//通过一个临时数组做存储，这样不需要使用temp对象做临时存储做转换，而是直接从最小的区块开始拷贝进去
temp[tempPos++] = arr[leftPos++];
else
temp[tempPos++] = arr[rightPos++];
}
while (leftPos <= leftEnd) { // 左边如果有剩余
temp[tempPos++] = arr[leftPos++];
}
while (rightPos <= rightEnd) { // 右边如果有剩余
temp[tempPos++] = arr[rightPos++];
}
// 最后一步进行复制，复制的只有更改的几个数字
for (int i = 0; i < numEle; i++) {
arr[rightEnd] = temp[rightEnd];
rightEnd--;
}
}
|
c实现
python实现