归并排序--Java版

阳光穿透心脏的1/2处 2023-10-17 15:03 113阅读 0赞

算法分析：

合并排序法主要是将两笔已排序的资料合并和进行排序。  
如果所读入的资料尚未排序，可以先利用其它的排序方式来处理这两笔资料，然后再将排序好的这两笔资料合并。

算法评价:

时间复杂度：T(n)=O(nlogn)  
空间复杂度：S(n)=O(n)

// 把两个有序的子序列进行归并
    	// 把a[left,mid] 和 a[mid+1,right] 归并到 b[left,right]
    	private void merge(int a[], int b[], int left, int mid, int rigth) {
    		// 游标p:遍历第一个子序列a[left,mid] ---当a[p]被选中放入b[]时，则p++
    		int p = left;
    		// 游标r:遍历第二个子序列a[mid+1,right] ---当a[r]被选中放入b[]时，则r++
    		int r = mid + 1;
    		// 把a[p]和a[r]当中小的数放到新空间b[k]中---k初始为left,每放入一个则k++
    		int k = left;
    		while (p <= mid && r <= rigth) {
    			if (a[p] < a[r]) {
    				b[k++] = a[p++];
    			} else {
    				b[k++] = a[r++];
    			}
    
    		}
    		// 经过上面的循环，一定是有一个序列已经被合并完，然后把另一个序列中剩下的那些元素直接搬到b[]
    		if (p > mid) {// 左序列排完，照搬右序列
    			for (int i = r; i <= rigth; i++) {
    				b[k++] = a[i];
    			}
    		} else {// 右序列排完，照搬左序列
    			for (int i = p; i <= mid; i++) {
    				b[k++] = a[i];
    			}
    		}
    
    	}

@Test
     	// 仅仅是测试merge方法 --------几段有序的数列可用
    	public void mergeSort_test() {
    		int a[] = { 1, 3, 5, 7, 11, 13, -1, 2, 4, 5, 8, 9 }; // 左右两段都是有序数列
    		int[] b = new int[a.length];
    		print(a);
    		merge(a, b, 0, 5, 11);
    		print(b);
    
    	}

测试结果:

1 3 5 7 11 13 -1 2 4 5 8 9 
    -1 1 2 3 4 5 5 7 8 9 11 13

// 对一个普通数组用归并算法排序:先分解再归并
    	private void MergeSort(int a[], int left, int rigth) {
    		if (left < rigth) {// 至少要有2个元素
    			// 分解
    			int mid = (left + rigth) / 2;
    			MergeSort(a, left, mid);
    			MergeSort(a, mid + 1, rigth);
    			// 再归并
    			int b[] = new int[a.length];// 临时空间，用于存储本次归并结果
    			merge(a, b, left, mid, rigth);
    			// 把b[left,right]中的数据对拷到a[left,right]
    
    			for (int i = left; i <= rigth; i++) {
    				a[i] = b[i];
    			}
    		}
    	}
    	
    
     @Test//测试mergeSort()方法
    	public void mergeSort_test2() {
    		int a[] = { 3, -5, 1, 3, 8, 2, 12, 100, 5, 7, 25, 4, 5, 11, 13, -1, 9 };
    		print(a);
    
    		MergeSort(a, 0, a.length - 1);
    		print(a);
    	}

![Center][]  
测试结果如下:

3 -5 1 3 8 2 12 100 5 7 25 4 5 11 13 -1 9 
    -5 -1 1 2 3 3 4 5 5 7 8 9 11 12 13 25 100

[Center]: https://img-blog.csdn.net/20170811224836904?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvU0hZTE9HTw==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center