Java排序算法總結之合並排序

Java排序算法總結之合並排序。本站提示廣大學習愛好者：（Java排序算法總結之合並排序）文章只能為提供參考，不一定能成為您想要的結果。以下是Java排序算法總結之合並排序正文

本文實例講述了Java排序算法總結之合並排序。分享給年夜家供年夜家參考。詳細剖析以下：

合並操作(merge)，也叫合並算法，指的是將兩個曾經排序的序列歸並成一個序列的操作。和疾速排序相似，讓我們一路來看，合並在Java中的完成。

合並排序（Merge）是將兩個（或兩個以上）有序表歸並成一個新的有序表，即把待排序序列分為若干個子序列，每一個子序列是有序的。然後再把有序子序列歸並為全體有序序列。

合並排序是樹立在合並操作上的一種有用的排序算法。該算法是采取分治法（Divide and Conquer）的一個異常典范的運用。 將已有序的子序列歸並，獲得完整有序的序列；即先使每一個子序列有序，再使子序列段間有序。若將兩個有序表歸並成一個有序表，稱為2-路合並。

合並排序算法穩固，數組須要O(n)的額定空間，鏈表須要O(log(n))的額定空間，時光龐雜度為O(nlog(n))，算法不是自順應的，不須要對數據的隨機讀取。

任務道理：

1、請求空間，使其年夜小為兩個曾經排序序列之和，該空間用來寄存歸並後的序列
2、設定兩個指針，最後地位分離為兩個曾經排序序列的肇端地位
3、比擬兩個指針所指向的元素，選擇絕對小的元素放入到歸並空間，並挪動指針到下一名置
4、反復步調3直到某一指針到達序列尾
5、將另外一序列剩下的一切元素直接復制到歸並序列尾

代碼完成：

////////////////
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];
 }
}

合並排序是比擬穩固的排序.即相等的元素的次序不會轉變.如輸出記載 1(1) 3(2) 2(3) 2(4) 5(5) (括號中是記載的症結字)時輸入的 1(1) 2(3) 2(4) 3(2) 5(5) 中的2 和 2 是按輸出的次序.這對要排序數據包括多個信息而要按個中的某一個信息排序,請求其它信息盡可能按輸出的次序分列時很主要.這也是它比疾速排序優勢的處所.

願望本文所述對年夜家的java法式設計有所贊助。