Java 詳細講解分治演演算法如何實現歸併排序

2022-04-06 19:04:00

1.什麼是分治演演算法

分治法

分治法，字面意思是「分而治之」，就是把一個複雜的1問題分成兩個或多個相同或相似的子問題，再把子問題分成更小的子問題直到最後子問題可以簡單地直接求解，原問題的解即子問題的解的合併，這個思想是很多高效演演算法的基礎，例如排序演演算法(快速排序，歸併排序)，傅立葉變換(快速傅立葉變換)等。

基本思想

分治法的基本思想：將一個難以直接解決的大問題，分割成一些規模較小的相同問題，以便各個擊破，分而治之。

2.分治演演算法的體現——歸併排序

歸併排序

歸併排序（ MERGE － SORT ）是利用歸併的思想實現的排序方法，該演演算法採用經典的分治（ divide - and - conquer )策略（分治法將問題分（ divide ）成一些小的問題然後遞迴求解，而治（ conquer ）的階段則將分的階段得到的各答案」修補」在一起，即分而治之）。

基本思想

流程圖（以對陣列[8,4,5,7,1,3,6,2]排序為例）

再來看看治階段，我們需要將兩個已經有序的子序列合併成一個有序序列，比如上圖中的最後一次合併，要將

[4,5,7,8］和［1,2,3,6］兩個已經有序的子序列，合併為最終序列［1,2,3,4,5,6,7,8]，來看下實現步驟。

3.程式碼實現

package Sort;
 
import java.util.Arrays;
/**
 * 歸併排序：
 * 
 * 利用歸併的思想實現的排序方法，該演演算法採用經典的分治（divide-and-conquer）策略（分治法將問題分(divide)成一些小的問題然後遞迴求解，
 * 
 * 而治(conquer)的階段則將分的階段得到的各答案"修補"在一起，即分而治之)。
 * @author lenovo
 *
 */
public class MergeSort {
	public static void main(String[] args) {
		int[] a= {5,8,6,3,9,8,7,1,4,21,-8,46};
		int[] temp=new int[a.length];
		mergeSort(a, 0, a.length-1, temp);
		System.out.println(Arrays.toString(a));
	}
	public static void mergeSort(int[] arr,int left,int right,int[] temp) {
		if(left<right) {
			int mid=(left+right)/2;
			mergeSort(arr, left, mid, temp);
			mergeSort(arr, mid+1,right, temp);
			merge(arr, left, mid, right, temp);
		}
	}
	public static void merge(int[] arr,int left,int mid,int right,int[] temp) {
		int l=left;//左邊序列的起始位置
		int r=mid+1;//右邊序列的起始位置
		int t=0;//中間陣列的當前元素下標
		while(l<=mid &&r<=right ) {//左邊或右邊沒結束
			//那邊小就將那邊的元素放入到臨時陣列中
			if(arr[l]<=arr[r]) {
				temp[t++]=arr[l++];
			}else {
				temp[t++]=arr[r++];
			}
		}
		//while迴圈結束，說明有一邊已經遍歷完畢，將另一邊剩餘的元素放入到臨時陣列中
		while(l<=mid) {
			temp[t++]=arr[l++];
		}
		while(r<=right) {
			temp[t++]=arr[r++];
		}
		//將臨時陣列中的有序序列copy到原陣列中
		t=0;
		int templeft=left;
		while(templeft<=right) {
			arr[templeft++]=temp[t++];
		}
	}
}

到此這篇關於Java 詳細講解分治演演算法如何實現歸併排序的文章就介紹到這了,更多相關Java 歸併排序內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！

Java 詳細講解分治演演算法如何實現歸併排序

目錄

1.什麼是分治演演算法

分治法

基本思想

2.分治演演算法的體現——歸併排序

歸併排序

基本思想

3.程式碼實現

熱門文章