【分治】归并排序

曾经终败给现在 2022-04-02 13:22 270阅读 0赞

**目录**

一、二路归并实现

二、二路归并的一点优化

三、原地归并实现

四、二路归并的非递归实现

五、在归并排序中使用直接插入排序

--------------------

## 一、二路归并实现 ##

递归实现，栈空间：O(logn)、堆空间：O(nlogn)

public static void mergeSort1(int[] arr) {  // 多做一层包装，简化用户输入
    		mergeSort1(arr, 0, arr.length-1);
    	}
    	public static void mergeSort1(int[] arr, int left, int right) {
    		int mid = (right+left) / 2;
    		if (left < right) {
    			mergeSort1(arr, left, mid);
    			mergeSort1(arr, mid+1, right);
    			merge1(arr, left, right, mid);
    		} 
    	}
    	public static void merge1(int[] arr, int left, int right, int mid) {
    		int[] temp = new int[right-left+1];
    		int i = left;
    		int j = mid+1;
    		int k = 0;
    		for (; i<=mid && j<=right; k++) {
    			if (arr[i] < arr[j]) {
    				temp[k] = arr[i];
    				i = i + 1;
    			} else {
    				temp[k] = arr[j];
    				j = j + 1;
    			}
    		}
    		// 两部分中哪一部分多出一些元素，就把该部分的所有元素直接加入temp数组
    		while (i <= mid) {
    			temp[k++] = arr[i++];
    		}
    		while (j <= right) {
    			temp[k++] = arr[j++];
    		}
    		
    		// 将排好序的temp数组的所有元素写入原数组的指定位置
    		for (int l=0; l<temp.length; l++) {
    			arr[left+l] = temp[l];
    		}
    	}

## 二、二路归并的一点优化 ##

上面的代码中因为每一趟都要新建一个数组temp来临时存放已经处理好的相对有序的数组，所以使用的堆空间为O(nlogn)。这里我们将使用的空间降到O(n)，也就是整个过程只新建一个大小为n的数组。

递归实现，栈空间：O(logn)、堆空间：O(n)

public static void mergeSort2(int[] arr) {
    		int[] temp = new int[arr.length];
    		mergeSort2(arr, temp, 0, arr.length-1);
    	}
    	public static void mergeSort2(int[] arr, int[] temp, int left, int right) {
    		int mid = (right+left) / 2;
    		if (left < right) {
    			mergeSort2(arr, temp, left, mid);
    			mergeSort2(arr, temp, mid+1, right);
    			merge2(arr, temp, left, right, mid);
    		} 
    	}
    	public static void merge2(int[] arr, int[] temp, int left, int right, int mid) {
    		int i = left;
    		int j = mid+1;
    		int k = left;
    		for (; i<=mid && j<=right; k++) {
    			if (arr[i] < arr[j]) {
    				temp[k] = arr[i];
    				i = i + 1;
    			} else {
    				temp[k] = arr[j];
    				j = j + 1;
    			}
    		}
    		// 两部分中哪一部分多出一些元素，就把该部分的所有元素直接加入temp数组
    		while (i <= mid) {
    			temp[k++] = arr[i++];
    		}
    		while (j <= right) {
    			temp[k++] = arr[j++];
    		}
    		
    		// 将排好序的temp数组的所有元素写入原数组的指定位置
    		for (int l=left; l<=right; l++) {
    			arr[l] = temp[l];
    		}
    	}

## 三、原地归并实现 ##

我们再继续将堆空间的复杂度降为O(1)

递归实现，栈空间：O(logn)、堆空间：O(1)

public static void mergeSort3(int[] arr) {
    		//int[] temp = new int[arr.length];
    		mergeSort3(arr, 0, arr.length-1);
    	}
    	public static void mergeSort3(int[] arr, int left, int right) {
    		int mid = (right+left) / 2;
    		if (left < right) {
    			mergeSort3(arr, left, mid);
    			mergeSort3(arr, mid+1, right);
    			merge3(arr, left, mid, right);
    		} 
    	}
    	public static void merge3(int[] arr, int left, int mid, int right) {
    		int i = left;
    		int j=mid+1;
    
    		/*
    		while (i<j && j<=right) {
    			int step = 0;
    			while (i<j && arr[i]<=arr[j]) {
    				++i;
    			}
    			while (j<=right && arr[j]<=arr[i]) {
    				++j;
    				++step;
    			}
    			reverseArray(arr, i, (j-1-step) , j-1);
    			i = i+step;
    		}
    		*/
    		
    
    		while (i<j && j<=right) {
    			//int step = 0;
    			while (i<j && arr[i]<=arr[j]) {
    				++i;
    			}
    			int index = j;
    			while (j<=right && arr[j]<=arr[i]) {
    				++j;
    				//++step;
    			}
    			//reverseArray(arr, i, (j-1-step) , j-1);
    			reverseArray(arr, i, index-1 , j-1);
    			//i = i+step;
    			i += (j-index);
    		}
    	}
    
    	public static void reverse(int[] arr, int left, int right) {
    		while (left < right) {
    			int temp = arr[left];
    			arr[left++] = arr[right];
    			arr[right--] = temp;
    		}
    	}
    	public static void reverseArray(int[] arr, int left, int mid, int right) {
    		reverse(arr, left, right);
    		int size1 = mid - left + 1;
    		int size2 = right-(mid+1) + 1;
    		int middle = left + size2 -1;
    		reverse(arr, left, left+size2-1);
    		reverse(arr, right-size1+1, right);
    	}

## 四、二路归并的非递归实现 ##

非递归实现，栈空间：O(1)、堆空间：O(nlogn)

public static void mergeSort4(int[] arr) {
    		int len = arr.length;
    		int k = 1;
    		
    		while (k < len) {
    			mergePass(arr, k, len);
    			k *= 2;
    		}
    	}
    	public static void mergePass(int[] arr, int k, int n) {
    		int i = 0;
    		int j;
    		
    		//从前往后，把2个（一对）长度为k的子序列合并为1个
    		while (i < n-2*k+1) {
    			merge(arr, i, i+k-1, i+2*k-1);
    			i += 2*k;
    		}
    		
    		//这段代码保证了，将那些“落单的”长度不足两两merge的部分和前面merge起来
    		if (i < n-k) {
    			merge(arr, i, i+k-1, n-1);
    		}
    	}
    	public static void merge(int[] arr, int low, int mid, int high) {
    		//temp数组用于暂存合并的结果
    		int[] temp = new int[high-low+1];
    		//左半边的指针
    		int i = low;
    		//后半边的指针
    		int j = mid+1;
    		//合并后数组的指针
    		int k = 0;
    		
    		//将记录从小到大（有序地）放进temp数组
    		for (; i<=mid && j<=high; k++) {
    			if (arr[i] <= arr[j]) {
    				temp[k] = arr[i++];
    			} else {
    				temp[k] = arr[j++];
    			}
    		}
    		//接下来的两个while循环是为了将一边剩余的（比另一边多出来的个数）放到temp数组中
    		while (i <= mid) {
    			temp[k++] = arr[i++];
    		}
    		while (j <= high) {
    			temp[k++] = arr[j++];
    		}
    		
    		//将temp数组中的元素写入原数组中的对应位置
    		for (int l=0; l<temp.length; l++) {
    			arr[low+l] = temp[l];
    		}
    	}

## 五、在归并排序中使用直接插入排序 ##

待续