- 内部排序之归并排序法
- 主要思想
- 2-路归并排序法
- 过程演示
- 递归过程
- 非递归过程
- JAVA代码
- 非递归实现
- 递归实现
- 算法分析
- 时间复杂度
- 空间复杂度
初始序列有n个元素记录，就可以看成 n n n个子序列，每个子序列的长度为 1 1 1，然后前后相邻的序列两两合并，得到 ⌈ n 2 ⌉ \lceil \frac{n}{2} \rceil ⌈2n⌉个长度为 2 2 2或为 1 1 1的有序子序列，在两两合并，直到得到一个长度为n的有序序列为止。
过程演示 递归过程
package sort;
import java.util.Arrays;
public class MergeSort {
public static void main(String[] args) throws Exception {
int[] o = {7, 6, 9, 3, 1, 5, 2, 4, 8};
System.out.print("排序前: ");
for (int t : o) {
System.out.print(t);
System.out.print(" ");
}
System.out.println();
// 算法部分
// 非递归的方式
nonRecursive(o);
System.out.print("排序后: ");
for (int t : o) {
System.out.print(t);
System.out.print(" ");
}
System.out.println();
}
public static void nonRecursive(int[] o) {
int[] temp = new int[o.length];
int gap = 1;
int count = 1;
while (gap = o.length) {
end2 = o.length - 1;
}
while (start1 0) {
result[i++] = right[0];
right = Arrays.copyOfRange(right, 1, right.length);
}
System.out.print("排序数组:");
for (int t : result) {
System.out.print(t);
System.out.print(" ");
}
System.out.println();
return result;
}
}
结果
排序前: 7 6 9 3 1 5 2 4 8
第1趟，每组元素个数：1，排序后: 6 7 3 9 1 5 2 4 8
第2趟，每组元素个数：2，排序后: 3 6 7 9 1 2 4 5 8
第3趟，每组元素个数：4，排序后: 1 2 3 4 5 6 7 9 8
第4趟，每组元素个数：8，排序后: 1 2 3 4 5 6 7 8 9
排序后: 1 2 3 4 5 6 7 8 9
package sort;
import java.util.Arrays;
public class MergeSort {
public static void main(String[] args) throws Exception {
int[] o = {7, 6, 9, 3, 1, 5, 2, 4, 8};
System.out.print("排序前: ");
for (int t : o) {
System.out.print(t);
System.out.print(" ");
}
System.out.println();
// 算法部分
// 递归的方式
o = sort(o);
System.out.print("排序后: ");
for (int t : o) {
System.out.print(t);
System.out.print(" ");
}
System.out.println();
}
public static void nonRecursive(int[] o) {
int[] temp = new int[o.length];
int gap = 1;
int count = 1;
while (gap = o.length) {
end2 = o.length - 1;
}
while (start1 0) {
result[i++] = right[0];
right = Arrays.copyOfRange(right, 1, right.length);
}
System.out.print("排序数组:");
for (int t : result) {
System.out.print(t);
System.out.print(" ");
}
System.out.println();
return result;
}
}
结果
排序前: 7 6 9 3 1 5 2 4 8
排序数组:6 7
排序数组:3 9
排序数组:3 6 7 9
排序数组:1 5
排序数组:4 8
排序数组:2 4 8
排序数组:1 2 4 5 8
排序数组:1 2 3 4 5 6 7 8 9
排序后: 1 2 3 4 5 6 7 8 9
对n个元素的序列进行归并排序，若 n > 1 n>1 n>1，T(n)=本次分组的合并时间加上，拆分成两个小组的比较合并时间，若 n = 1 n=1 n=1,即有序了。所花时间可能就是一个常数C。则 T ( n ) = { C n = 1 n + 2 T ( n 2 ) n > 1 T(n)= \begin{cases} \vcenter C &{n = 1} \\ n+2T(\frac{n}{2}) &{n >1 } \end{cases} T(n)={Cn+2T(2n)n=1n>1
∴ T ( n ) = n + 2 T ( n 2 ) = n + 2 ( n 2 + 2 T ( n 4 ) ) = 2 n + 4 T ( n 4 ) = n + 2 ( n 2 + 2 ( n 4 + 2 T ( n 8 ) ) ) = 3 n + 8 T ( n 8 ) . . . = k n + 2 k ∗ T ( n 2 k ) 当 n 2 k = 1 时，分组达到最后一层，即 k = l o g 2 n 原式 = n ∗ l o g 2 n + 2 l o g 2 n ∗ C = n l o g 2 n + C ∗ N ⟹ O ( n l o g 2 n ) \begin{aligned} \therefore T(n)&=n+2T(\frac{n}{2}) \\ &=n+2(\frac{n}{2}+2T(\frac{n}{4}))=2n+4T(\frac{n}{4}) \\ &=n+2(\frac{n}{2}+2(\frac{n}{4}+2T(\frac{n}{8})))=3n+8T(\frac{n}{8})\\ &.\\ &.\\ &.\\ &=kn+2^k*T(\frac{n}{2^k})\\ 当\frac{n}{2^k}&=1时，分组达到最后一层，即k=log_2^n \\ 原式&=n*log_2^n+2^{log_2^n}*C \\ &=nlog_2^n+C*N \implies \boxed{O(nlog_2^n)}\\ \end{aligned} ∴T(n)当2kn原式=n+2T(2n)=n+2(2n+2T(4n))=2n+4T(4n)=n+2(2n+2(4n+2T(8n)))=3n+8T(8n)...=kn+2k∗T(2kn)=1时，分组达到最后一层，即k=log2n=n∗log2n+2log2n∗C=nlog2n+C∗N⟹O(nlog2n)
由于归并排序的算法跟有序度无关，所以时间复杂度很稳定都是 O ( n l o g 2 n ) O(nlog_2^n) O(nlog2n)；
空间复杂度在算法实现中，需要申请与长度不超过 n n n的空间使用。其空间复杂度为 O ( n ) O(n) O(n)。
