快捷導(dǎo)航

Java排序算法總結(jié)之歸并排序

更新時(shí)間：2015年05月19日 10:56:05 作者：一羽清寧

這篇文章主要介紹了Java排序算法總結(jié)之歸并排序,較為詳細(xì)的分析了歸并排序的原理與java實(shí)現(xiàn)技巧,需要的朋友可以參考下

本文實(shí)例講述了Java排序算法總結(jié)之歸并排序。分享給大家供大家參考。具體分析如下：

歸并操作(merge)，也叫歸并算法，指的是將兩個(gè)已經(jīng)排序的序列合并成一個(gè)序列的操作。和快速排序類似，讓我們一起來看，歸并在Java中的實(shí)現(xiàn)。

歸并排序（Merge）是將兩個(gè)（或兩個(gè)以上）有序表合并成一個(gè)新的有序表，即把待排序序列分為若干個(gè)子序列，每個(gè)子序列是有序的。然后再把有序子序列合并為整體有序序列。

歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為2-路歸并。

歸并排序算法穩(wěn)定，數(shù)組需要O(n)的額外空間，鏈表需要O(log(n))的額外空間，時(shí)間復(fù)雜度為O(nlog(n))，算法不是自適應(yīng)的，不需要對數(shù)據(jù)的隨機(jī)讀取。

工作原理：

1、申請空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來存放合并后的序列
2、設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置
3、比較兩個(gè)指針?biāo)赶虻脑?，選擇相對小的元素放入到合并空間，并移動指針到下一位置
4、重復(fù)步驟3直到某一指針達(dá)到序列尾
5、將另一序列剩下的所有元素直接復(fù)制到合并序列尾

代碼實(shí)現(xiàn)：

////////////////
public void mergeSort(){
 long[] workSpace = new long[nElems];
 recMergeSort(workSpace,0,nElems-1);
}
private void recMergeSort(long[] workSpace,int lowerBound,int upperBound){
 if(lowerBound == upperBound){
  return;
 }
 else{
  int mid=(lowerBound+upperBound)/2;
  recMergeSort(workSpace, lowerBound, mid);
  recMergeSort(workSpace, mid+1, upperBound);
  merge(workSpace, lowerBound, mid+1, upperBound);
 }
}
private void merge(long[] workSpace,int lowPtr,int highPtr,int upperBound){
 int j = 0;
 int lowerBound = lowPtr;
 int mid = highPtr - 1;
 int n = upperBound-lowerBound+1;
 while(lowPtr<=mid&&highPtr<=upperBound){
  if(theArray[lowPtr]<theArray[highPtr]){
  workSpace[j++]=theArray[lowPtr++];
  }
  else{
  workSpace[j++]=theArray[highPtr++];
  }
 }
 while(lowPtr<=mid){
  workSpace[j++] = theArray[lowPtr++];
 }
 while(highPtr<=upperBound){
  workSpace[j++] = theArray[highPtr++];
 }
 for(j=0;j<n;j++){
  theArray[lowerBound+j]=workSpace[j];
 }
}

歸并排序是比較穩(wěn)定的排序.即相等的元素的順序不會改變.如輸入記錄 1(1) 3(2) 2(3) 2(4) 5(5) (括號中是記錄的關(guān)鍵字)時(shí)輸出的 1(1) 2(3) 2(4) 3(2) 5(5) 中的2 和 2 是按輸入的順序.這對要排序數(shù)據(jù)包含多個(gè)信息而要按其中的某一個(gè)信息排序,要求其它信息盡量按輸入的順序排列時(shí)很重要.這也是它比快速排序優(yōu)勢的地方.

希望本文所述對大家的java程序設(shè)計(jì)有所幫助。

您可能感興趣的文章: