归并排序

红太狼 2024-04-19 11:34 2阅读 0赞

归并排序思想：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1YWl4aWFvaGFpXzE_size_16_color_FFFFFF_t_70][]

归并排序有两种思路，但是他们最后都是把这个数组分为一个一个的，然后开始归并。

归并排序的重点就是归并这个步骤，不断扩大归并长度，然后不断进行归并。

归并排序自下向上实现（2路归并）：

public class 归并排序自下向上 {
    
    	public static void main(String[] args) {
    		归并排序自下向上 test = new 归并排序自下向上();
    		int a[] = { 1, 9, 20, 23, 34, 2, 3, 45, 12, 43 };
    		test.MergeSort(a, a.length - 1);
    		for (int i : a) {
    			System.out.print(i + "  ");
    		}
    	}
    
    	public void MergeSort(int a[], int n) {
    		int b[] = new int[a.length];
    		// 归并步数
    		int s = 1;
    		while (s < n) {
    			//归并一次存到b数组中
    			MergePass(a, b, s, n);
    			s += s;
    			//再次归并，返回到a中 
    			MergePass(b, a, s, n);
    			s += s;
    		}
    	}
    
    	private void MergePass(int[] a, int[] b, int s, int n) {
    		int i = 0;
    		while (i < n - 2 * s) {
    			Merge(a, b, i, i + s - 1, i + 2 * s - 1);
    			i = i + 2 * s;
    		}
    		// 讨论如果不够分的部分
    		if (i + s < n) {
    			// 够2路
    			Merge(a, b, i, i + s - 1, n - 1);
    		} else {
    			// 不够两路
    			for (int j = i; j <= n - 1; j++) {
    				b[j] = a[j];
    			}
    		}
    	}
    
    	// 归并
    	private void Merge(int[] a, int[] b, int left, int mid, int right) {
    		int rightjudge = mid + 1, j = left;
    		while (left <= mid && rightjudge <= right) {
    			if (a[left] < a[rightjudge]) {
    				b[j] = a[left];
    				left++;
    			} else {
    				b[j] = a[rightjudge];
    				rightjudge++;
    			}
    			j++;
    		}
    		while (left <= mid) {
    			b[j++] = a[left++];
    		}
    		while (rightjudge <= right) {
    			b[j++] = a[rightjudge++];
    		}
    	}
    }

结果：

1  2  3  9  12  20  23  34  45  43

归并排序自上向下（递归）：

public class 归并排序自顶向下 {
    	private static int[] b ;
    	
    	public static void main(String[] args) {
    		int a[] = {1,9,20,23,34,2,3,45,12,43};
    		b= new int[a.length];
    		归并排序自顶向下  test = new 归并排序自顶向下();
    		test.MergeSort(a, 0,a.length-1);
    		for (int i : a) {
    			System.out.print(i+"  ");
    		}
    	}
    	
    	public void MergeSort(int[] a,int left,int right) {
    		if(left<right) {
    			//找中点
    			int i = (left+right)/2;
    			//排左边
    			MergeSort(a,left,i);
    			//排右边
    			MergeSort(a,i+1,right);
    			//归并
    			Merge(a,b,left,i,right);
    			Copy(a,b,left,right);
    		}
    	}
    	
    	private void Copy(int[] a, int[] b, int left, int right) {
    		for(int i=left;i<=right;i++) {
    			a[i]=b[i];
    		}
    	}
    
    	//归并
    	private void Merge(int[] a, int[] b, int left,int mid, int right) {
    		int rightjudge = mid+1,j=left;
    		while(left<=mid&&rightjudge<=right) {
    			if(a[left]<a[rightjudge]) {
    				b[j]=a[left];
    				left++;
    			}else {
    				b[j]=a[rightjudge];
    				rightjudge++;
    			}
    			j++;
    		}
    		while(left<=mid) {
    			b[j++]=a[left++];
    		}
    		while(rightjudge<=right) {
    			b[j++]=a[rightjudge++];
    		}
    	}
    }

1  2  3  9  12  20  23  34  43  45

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1YWl4aWFvaGFpXzE_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/a64eb4b37b344eed8f07319a6daba3d2.png