【java数据结构与算法学习】归并排序

梦里梦外; 2022-05-29 08:29 220阅读 0赞

今天我们来记录一下归并排序。

归并排序的主要思想：

将数组分成两半，将每一半排好序，然后分别在每一半数组的开头设置指针，进行比较，小的就放在辅助数组中，该指针往下移，直到其中一边的数组走到头，将剩余的元素拷贝到辅助数组中，返回数组就是有序数组。

根据master公式O(T) = aO(T/b) + O(N^d)可知，a = 2,b = 2,d = 1 。a/b = d,所以归并排序的时间复杂度是O(N\*logN)的。

public class MergeSort {
    	
    	public static void mergeSort(int[] arr) {
    		//如果数组是空，或者元素小于2，那么不用排序，直接返回
    		if (arr == null || arr.length < 2) {
    			return;
    		}
    		sortProcess(arr, 0, arr.length - 1);
    		
    	}
    	public static void sortProcess(int[] arr, int L, int R) {
    		//递归结束条件，当只有一个元素的时候，不用排序，返回
    		if (L == R) {
    			return;
    		}
    		int mid = L + ((R-L) >> 1);//相当于(L + R) / 2,求中点位置 
    		//让左边有序
    		sortProcess(arr, L, mid);
    		//让右边有序
    		sortProcess(arr, mid + 1, R);
    		//归并过程
    		merge(arr, L, mid, R);
    	}
    	
    	public static void merge(int[] arr, int L, int mid, int R) {
    		//辅助数组
    		int[] help = new int[R - L + 1];
    		//辅助数组下标
    		int i = 0;
    		//p1指针指向左半部分第一个元素
    		int p1 = L;
    		//p2指针指向右半部分第一个元素
    		int p2 = mid + 1;
    		//如果两个指针都没有越界
    		while (p1 <= mid && p2 <= R){
    			//比较最小值，放入辅助数组
    			if(arr[p1] < arr[p2]) {
    				help[i++] = arr[p1++];
    			}else {
    				help[i++] = arr[p2++];
    			}
    		}
    		//如果有一个指针越界了，将另一部分剩余的元素直接拷贝到辅助数组中
    		while(p1 <= mid) {
    			help[i++] = arr[p1++];
    		}
    		while(p2 <= R) {			
    			help[i++] = arr[p2++];
    		}
    		//将辅助数组中的元素拷贝会原数组
    		for(int j = 0;j<help.length; j++) {
    			arr[L++] = help[j];
    		}
    		
    	}
    	
    	public static void main(String[] args) {
    		
    		int[] arr = new int[] {2,5,88,26,1,85,99,2,0};
    		
    		mergeSort(arr);
    		
    		for (int i : arr) {
    			System.out.print(i + " ");
    		}
    	}
    }