排序算法二：归并排序(Merge sort)
归并排序(Merge sort)用到了分治思想，即分-治-合三步，算法平均时间复杂度是O(nlgn).
（一）算法实现
private void merge_sort(int[] array, int first, int last) {
if (first + 1 < last) {
int mid = (first + last) / 2;
merge_sort(array, first, mid);
merge_sort(array, mid, last);
// merge
int i = first;
int j = mid;
int[] tempArray = new int[last - first];
for (int k = 0; k < tempArray.length; k++) {
if (j == last) {
tempArray[k] = array[i++];
} else if (i == mid) {
tempArray[k] = array[j++];
} else if (array[i] <= array[j]) {
tempArray[k] = array[i++];
} else if (array[i] > array[j]) {
tempArray[k] = array[j++];
} else {
throw new RuntimeException("Merge sort error.");
}
}
System.arraycopy(tempArray, 0, array, first, last - first);
}
}
Merge sort
1）算法不是原地排序，合并时需要额外空间
2）算法平均时间复杂度是O(nlgn)
3）归并排序属于比较排序
4）归并排序属于稳定排序算法
（二）仿真结果
**************************************************
Number to Sort is:2500
Array to sort is:{633649,71377,977368,56277,635475,755791,746668,373470,820128,669757...}
Cost time of 【MergSort】 is(milliseconds):1
Sort result of 【MergSort】:{695,711,935,1074,1571,1681,2434,3967,4104,4452...}
**************************************************
Number to Sort is:25000
Array to sort is:{62806,677129,876202,279782,662046,978299,979879,374196,303999,484652...}
Cost time of 【MergSort】 is(milliseconds):5
Sort result of 【MergSort】:{15,34,74,94,131,141,316,372,375,417...}
**************************************************
Number to Sort is:250000
Array to sort is:{617507,750026,202102,267444,690991,638097,868240,413838,774218,463780...}
Cost time of 【MergSort】 is(milliseconds):67
Sort result of 【MergSort】:{6,9,19,28,31,39,44,45,56,59...}
相关代码：
package com.cnblogs.riyueshiwang.sort;
import java.util.Arrays;
public class MergeSort extends abstractSort {
@Override
protected void sort(int[] toSort) {
merge_sort(toSort, 0, toSort.length);
}
private void merge_sort(int[] array, int first, int last) {
if (first + 1 < last) {
int mid = (first + last) / 2;
merge_sort(array, first, mid);
merge_sort(array, mid, last);
// merge
int i = first;
int j = mid;
int[] tempArray = new int[last - first];
for (int k = 0; k < tempArray.length; k++) {
if (j == last) {
tempArray[k] = array[i++];
} else if (i == mid) {
tempArray[k] = array[j++];
} else if (array[i] <= array[j]) {
tempArray[k] = array[i++];
} else if (array[i] > array[j]) {
tempArray[k] = array[j++];
} else {
throw new RuntimeException("Merge sort error.");
}
}
System.arraycopy(tempArray, 0, array, first, last - first);
}
}
public static void main(String[] args) {
for (int j = 0, n = 2500; j < 3; j++, n = n * 10) {
System.out
.println("**************************************************");
System.out.println("Number to Sort is:" + n);
int[] array = CommonUtils.getRandomIntArray(n, 1000000);
System.out.print("Array to sort is:");
CommonUtils.printIntArray(array);
int[] array1 = Arrays.copyOf(array, n);
new MergeSort().sortAndprint(array1);
}
}
}
MergeSort.java
最新文章
- Maven安装
- SecWeek
- NTDLL未文档化函数RtlGetNtVersionNumbers获取操作系统版本
- Android入门(二)Activity-Toast、Intent
- 序列GCD和问题(题目)
- BZOJ 2433 智能车比赛（计算几何+最短路）
- Java泛型方法定义及泛型类型推断
- poj1185：炮兵阵地（状压dp）
- ISO9126 质量模型
- 对于ios7扫描二维码功能的实现
- Tomcat启动中的一些问题
- java的输出类
- day43 mysql 基本管理,[破解密码以及用户权限设置]以及慢日志查询配置
- 【开源】C#信息抽取系统【招募C#队友】
- 查找->动态查找表->平衡二叉树
- Win10系列：VC++ Direct3D开发基础1
- sql server ldf 日志文件清理
- where_1
- 开源通用爬虫框架YayCrawler-运行与调试
- (原)在firefly_rk3288开发板上解决openGL在设置32位色深以后出现花屏的问题