一. 算法描述

歸并排序采用了分治策略(divide-and-conquer)，就是將原問(wèn)題分解為一些規(guī)模較小的相似子問(wèn)題，然后遞歸解決這些子問(wèn)題，最后合并其結(jié)果作為原問(wèn)題的解。

歸并排序?qū)⒋判驍?shù)組A[1..n]分成兩個(gè)各含n/2個(gè)元素的子序列，然后對(duì)這個(gè)兩個(gè)子序列進(jìn)行遞歸排序，最后將這兩個(gè)已排序的子序列進(jìn)行合并，即得到最終排好序的序列。具體排序過(guò)程如下圖所示：

歸并排序中一個(gè)很重要的部分是兩個(gè)已排序序列合并的過(guò)程，這里需要另外開辟一塊新的空間來(lái)作為存儲(chǔ)這兩個(gè)已排序序列的臨時(shí)容器。假設(shè)對(duì)A[p..r]序列進(jìn)行合并，已知A[p..q]及A[q+1..r]為已排序的序列，合并的具體步驟為：

Step 1：新建兩個(gè)數(shù)組L、R分別存儲(chǔ)待合并序列A[p..q]和A[q+1..r]，將待排序序列中的對(duì)應(yīng)元素copy到L和R中，L和R最后設(shè)置一個(gè)極大值作為“哨兵”；

Step 2：令指針i指向L的起始元素，j指向R的起始元素，k指向A待合并部分的起始元素A[p]；

Step 3：若L[i]≤R[j]，令A(yù)[k]=L[i]，i=i+1，k=k+1；

否則，令A(yù)[k]=R[j]，j=j+1，k=k+1；

(這一步即依次比較i、j所指向的元素，將較小值依次放入到A中相應(yīng)位置。)

Step 4 ：重復(fù)Step 3，r-p+1次后停止，即依次確定A[p..q]每個(gè)位置上的元素。

經(jīng)過(guò)合并操作后，A[p..q]為一個(gè)有序序列。若待合并序列為(38， 49， 65， 97， 13， 27， 49， 76)，p=1，q=4,， r=8，即A[1..4]和A[5..8]分別為有序序列，則合并操作的具體過(guò)程如下圖所示：

package com.neuedu.algorithm;

import java.util.Arrays;

public class MergeSort {

//歸并排序

/*歸并排序采用遞歸實(shí)現(xiàn)

* 分階段可以理解為就是遞歸拆分子序列的過(guò)程、

* 治階段，我們需要將兩個(gè)已經(jīng)有序的子序列合并成一個(gè)有序序列，比如上圖中的最后一次合并，要將[4,5,7,8]和[1,2,3,6]兩個(gè)已經(jīng)有序的子序列，合并為最終序列[1,2,3,4,5,6,7,8]，

* */

public static void main(String []args){

int []arr = {9,8,7,6,5,4,3,2,1};

sort(arr);

System.out.println(Arrays.toString(arr));

}

public static void sort(int []arr){

int []temp = new int[arr.length];//在排序前，先建好一個(gè)長(zhǎng)度等于原數(shù)組長(zhǎng)度的臨時(shí)數(shù)組，避免遞歸中頻繁開辟空間

sort(arr,0,arr.length-1,temp);

}

private static void sort(int[] arr,int left,int right,int []temp){

if(left

int mid = (left+right)/2;

sort(arr,left,mid,temp);//左邊歸并排序，使得左子序列有序

sort(arr,mid+1,right,temp);//右邊歸并排序，使得右子序列有序

merge(arr,left,mid,right,temp);//將兩個(gè)有序子數(shù)組合并操作

}

}

private static void merge(int[] arr,int left,int mid,int right,int[] temp){

int i = left;//左序列指針

int j = mid+1;//右序列指針

int t = 0;//臨時(shí)數(shù)組指針

while (i<=mid && j<=right){

if(arr[i]<=arr[j]){

temp[t++] = arr[i++];

}else {

temp[t++] = arr[j++];

}

}

while(i<=mid){//將左邊剩余元素填充進(jìn)temp中

temp[t++] = arr[i++];

}

while(j<=right){//將右序列剩余元素填充進(jìn)temp中

temp[t++] = arr[j++];

}

t = 0;

//將temp中的元素全部拷貝到原數(shù)組中

while(left <= right){

arr[left++] = temp[t++];

}

}

}

總結(jié)

以上是生活随笔為你收集整理的java的归并排序算法_归并排序算法Java实现的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。