十大排序算法之归并排序

刺骨的言语ヽ痛彻心扉 2024-04-18 10:56 13阅读 0赞

例题：  
对a\[\]=\{3,44,38,5,47,15,36,26,27,2,46,4,19,50,48\}排序  
要求从小到大排列。

介绍：  
归并排序用到了分治的思想，  
顾名思义，分而治之  
一个长数组的排序不好搞定，  
我们可以把一个数组分为两个小规模的问题，  
一直切分下去，直到排序问题变为比较两个元素大小的问题  
我们只需要对两个元素进行排序后再进行合并即可完成任务。

难点：  
归并排序的合并问题是最难以搞定的  
我们可以开辟一个新的空间，用来承载我们的两个小数组，  
分别定义两枚指针在两个小数组的左端，  
每取出一个元素即将该指针右移一位，  
直到两枚指针均走到所在数组的末尾。

执行：  
将大问题分解为小区间问题  
解决小问题  
对小问题进行合并。  
![在这里插入图片描述][20190905180537726.gif]  
评价：  
时间复杂度O（n log n）；  
需要占用少量空间。  
java代码：

package 日常练习;
    
    import java.util.Arrays;
    
    public class 归并排序 {
    	public static void sort(int[] arr) {
    		int[] temp = new int[arr.length];// 在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
    		sort(arr, 0, arr.length - 1, temp);// 开启排序算法对数组排序
    	}
    
    	private static void sort(int[] arr, int left, int right, int[] temp) {
    		if (left < right) {
    			int mid = (left + right) / 2;// 找出重点作为分割点
    			sort(arr, left, mid, temp);// 左边归并排序，使得左子序列有序
    			sort(arr, mid + 1, right, temp);// 右边归并排序，使得右子序列有序
    			merge(arr, left, mid, right, temp);// 将两个有序子数组合并操作
    		}
    	}
    
    	private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
    		int i = left;// 左序列指针
    		int j = mid + 1;// 右序列指针
    		int t = 0;// 临时数组指针
    		// 根据指针从两个区间内由小到大取值
    		while (i <= mid && j <= right) {
    			if (arr[i] <= arr[j]) {
    				temp[t++] = arr[i++];
    			} else {
    				temp[t++] = arr[j++];
    			}
    		}
    		// 当右边区间内取完时
    		// 将左边剩余元素填充进temp中
    		while (i <= mid) {
    			temp[t++] = arr[i++];
    		}
    		// 当左边区间内取完时
    		// 将右序列剩余元素填充进temp中
    		while (j <= right) {
    			temp[t++] = arr[j++];
    		}
    		t = 0;
    		// 完成两个小数组的合并后
    		// 将temp中的元素全部拷贝到原数组中
    		while (left <= right) {
    			arr[left++] = temp[t++];
    		}
    	}
    	public static void main(String[] args) {
    		int arr[] = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
    		sort(arr);
    		System.out.println(Arrays.toString(arr));
    	}
    
    }

[20190905180537726.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/187afb5c82e547bcad7c5717eb66101c.gif