数据结构之排序算法——归并排序（Java实现）

今天药忘吃喽~ 2023-03-12 10:51 3阅读 0赞

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

➢ **思路分析图解**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70]  
其中治的部分实现图解：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 1]  
➢ **代码实现**  
使用俩个方法，分别实现分治。

// 分
    	public static void branch(int[] arr, int left, int right, int[] temp) { 
    		if (left < right) { 
    			int mid = (left + right) / 2;
    			// 向左递归进行分解
    			branch(arr, left, mid, temp);
    			// 向右进行递归
    			branch(arr, mid + 1, right, temp);
    			// 直接合并
    			cure(arr, left, mid, right, temp);
    		}
    	}
    
    	// 治 , 合并的次数是arr.lrngth次
    	public static void cure(int[] arr, int left, int middle, int right, int[] temp) { 
    		// left 左边初始索引
    		// middle 中间索引
    		// right 右边索引
    		// temp 中间变量数组
    
    		// 初始化i和j,左右俩边的初始索引，用于“治”
    		int i = left;
    		int j = middle + 1;
    		int t = 0; // 指向中间变量数组的最开始位置
    
    		// 第一步：把左右俩边的数据进行比较添加到temp，直到一方为0即处理完毕
    		while (i <= middle && j <= right) { 
    			if (arr[i] < arr[j]) { 
    				temp[t] = arr[i];
    				t++;
    				i++;
    			} else { 
    				temp[t] = arr[j];
    				t++;
    				j++;
    			}
    		}
    		// 第二步：若一方有剩余，依次全部添加到temp当中。
    		while (i <= middle) { 
    			// 左边剩余
    			temp[t] = arr[i];
    			t++;
    			i++;
    		}
    		while (j <= right) { 
    			temp[t] = arr[j];
    			t++;
    			j++;
    		}
    		// 第三步：把中间变量数组重新写入到arr数组
    		t = 0;
    		int templeft = left;
    		while (templeft <= right) { 
    			arr[templeft] = temp[t];
    			templeft++;
    			t++;
    		}
    	}

调用方法进行测试：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 2]  
和以前一样测试一下这个算法的效率：测试10000000个数据，基本在俩三秒内就可以排完序。

int[] arr1 = new int[10000000];
    		int temp [] = new int [arr1.length];
    		for (int i = 0; i < 10000000; i++) { 
    			arr1[i] = (int) (Math.random() * 100000000); // 生成一个[0,1000000) 的随机数
    		}
    		Date a = new Date();
    		SimpleDateFormat SimpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
    		String a1 = SimpleDateFormat.format(a);
    		System.out.println("排序前：" + a1);
    		branch(arr1, 0, arr1.length-1, temp);
    
    		Date b = new Date();
    		String b1 = SimpleDateFormat.format(b);
    		System.out.println("排序后：" + b1);

如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 3]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70]: /images/20230312/76cb657914d24cfca025897c96c184f0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 1]: /images/20230312/f19b09d77c4349298cfc0e16758f8157.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 2]: /images/20230312/16b21e827f344783ba8116f8274cbd1d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 3]: /images/20230312/032ae858b15642f9a4dbb2a3f4f17494.png