排序算法之归并排序

1. 归并排序

​ 归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的 分治 （divide-and-conquer ）策略（分治法将问题分(divide)成一些 小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案”修
补”在一起，即分而治之)。

1.1 归并排序思想示意图

1.1.1 合并相邻有序子序列

由上图可知分的阶段逻辑相当简单，那我们仔细看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]。

1.2 实现归并排序的分-治

对数组, int[] arr ={8, 4, 5, 7, 1, 3, 6, 2 } ,使用归并排序完成排序。

  • public static void mergetSort(int[] arr,int left,int right,int[] temp);分的方法
  • public static void merget(int[] arr,int left,int mid,int right,int[] temp); * 合并的方法
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
/**
 *  分加和的方法
 * @param arr
 * @param left
 * @param right
 * @param temp
 */
public static void mergetSort(int[] arr,int left,int right,int[] temp) {
	if(left < right) {
		
		int mid = (left + right)/2;//中间的索引
		
		mergetSort(arr, left, mid, temp);//向左递归进行分解
		
		mergetSort(arr, mid+1, right, temp);//向右递归开始分解
		
		merget(arr, left, mid, right, temp);//合并
		
	}
}

/**
 *   合并的方法
 * @param arr 排序的原始数组
 * @param left 左边的有序序列的初始索引
 * @param mid 中间索引
 * @param right 右边索引
 * @param temp 中转数组
 */
public static void merget(int[] arr,int left,int mid,int right,int[] temp) {
	
	int i = left;// 初始化i,左边有序序列的的初始索引
	int j = mid + 1;//初始化j,右边有序序列的初始索引
	int t = 0;//指向temp数组的当前索引
	
	//先把左右两边的数据按照规则填充到temp数组中，直到左右两边的有序序列有一边处理完毕为止
	while(i<=mid && j<=right) {
		
		//如果左边的有序序列的当前元素，小于等于右边有序序列的当前元素
		//即将左边的当前元素，填充到 temp 数组
		//左半部分
		if(arr[i]<=arr[j]) {
			temp[t] = arr[i];
			t +=1;
			i +=1;
			
		}else {//反之
			temp[t] = arr[j];
			t +=1;
			j +=1;
		}
		   
	}
	
	//把所有剩余数据的一边的数据依次全部填充到temp中
	
	while(i<=mid) { //左边的有序序列还有剩余的元素，就全部填充到 temp
		temp[t] = arr[i];
		t +=1;
		i +=1;
	}
	
	while(j<=right) {//对右边数据的处理
		temp[t] = arr[j];
		t +=1;
		j +=1;
	}
	
	
	
	//将temp数据的元素拷贝到arr--并不是每次都是拷贝所有
	t = 0;
	int tempLeft = left;
	while(tempLeft<=right) {
		arr[tempLeft] = temp[t];
		t +=1;
		tempLeft +=1;
	}
	
}

1.3 测试结果及速度

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
public class MergetSort {
	/**
	 * 8w-->1s不到
	 * 80w-->1s不到
	 * 800w-->1-2s
	 * 8000w-->22s左右
	 * @param args
	 */
	public static void main(String[] args) {
		//int[] arr = {8,4,5,7,1,3,6,2};
		 int[] arr = new int[80000000]; 
		 for (int i = 0; i < 80000000; i++) { 
			 arr[i] =(int)(Math.random()*800000); 
		 } 
		 
		 Date date1 = new Date(); SimpleDateFormat
		 simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
		 
		 String format1 = simpleDateFormat.format(date1);
		 System.out.println("排序前的时间："+format1);
		 
		 int[] temp = new int[arr.length];
		 mergetSort(arr, 0, arr.length-1, temp);
		
		 Date date2 = new Date();
		 String format2 = simpleDateFormat.format(date2);
		 System.out.println("排序后的时间："+format2);
		
	
		//System.out.println(Arrays.toString(arr));
		
	}
}