為什么使用歸并排序？?

java中的Arrays.sort(Object[] o)是對數組進行排序，它使用的是歸并排序的方式，?
快速排序要比歸并排序更快一些，但為什么使用歸并排序了？原因是歸并排序是一種穩定的排序?
方式，即歸并排序不交換相同的元素，這就意味著，在按一種方式排序后同時可以按另外一種?
方式進行排序。比如員工可以首先按工資排序，然后按名字排序，一種排序不會打亂另一種排序?
的順序。?
下面分析下sort方法的簡化版： /**
? ? ?* 歸并排序 (遞歸實現)
? ? ?* 前提： 每個元素要有可比性，這里元素必須實現Comparable接口。
? ? ?* 基本原理為：1.拆分 假設有N個元素的列表，首先把它拆分成2個或2個
? ? ?* 以上的元素組成的新的列表(這里我的新列表長度不超過3)，分別對對它們進行排序。
? ? ?* 2.歸并。把所有的排好序的子類表兩兩歸并，如此重復，直到歸并成一個含N個
? ? ?* 元素的有序列表為止
? ? ?* 圖解：(大于3就繼續分解)
? ? ?* ?大于3 ? ? ? ? ?8 ? ?7 ? ?6 ? ?5 ? ? 4 ? ? 3 ? ? 2 ? ? 1
? ? ?* ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?分|解
? ? ?* ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?|
? ? ?* ?大于3 ? ? ? ? ? ?8 ?7 ?6 ?5 ? ? ? ? ? ?4 ? 3 ? 2 ? 1?
? ? ?* ? ? ? ? ? ? ? ? ? ? 分|解 ? ? ? ? ? ? ? ? ?分|解
? ? ?* ? ? ? ? ? ? ? ? ? ? ? | ? ? ? ? ? ? ? ? ? ? ?|?
? ? ?* ?小于 3 ? ? ? ? ? ?8 7 ? 6 5 ? ? ? ? ? ? 4 ?3 ? ?2 1
? ? ?* ?排序 ? ? ? ? ? ? ?7 8 ? 5 6 ? ? ? ? ? ? 3 ?4 ? ?1 2?
? ? ?* ?歸并 ? ? ? ? ? ? ? ? | ? ? ? ? ? ? ? ? ? ? ? |?
? ? ?* ? ? ? ? ? ? ? ? ?7 ? 8 ?5 ?6 ? ? ? ? ? ?3 ?4 ? ?1 ?2?
? ? ?* ? ? ? ? ? ? ? ? ? ? ? | ? ? ? ? ? ? ? ? ? ? ? |
? ? ?* ?順序保存 ? ? ? ?5 ? 6 ?7 ?8 ? ? ? ? ? ?1 ?2 ? ?3 ?4
? ? ?* ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? |
? ? ?* ?歸并 ? ? ? ? ? 5 ? ?6 ? ?7 ? ?8 ? 1 ? ?2 ? ?3 ? ? 4
? ? ?* ? |
? ? ?* ?順序保存 ? ? ? 1 ? ?2 ? ?3 ? ?4 ? 5 ? ?6 ? ?7 ? ? 8
? ? ?* @param src 臨時中間數組，它是目標數組的拷貝
? ? ?* @param target 目標排序數組
? ? ?* @param low 需排序的起始索引
? ? ?* @param high 需排序的結束索引
? ? ?*?
? ? ?*/
? ? public static void mergeSort(Object[] src,Object[] dest,int low,int high){
? ? int length = high - low;
? ? if(length < 3 ){ //對長度小于3的列表排序
? ? //排序方法一：起泡排序(大數沉底)
// ? ? for(int i=low;i<high-1;i++){
// ? ? for(int j=low;j<high-1-i+low;j++){
// ? ? if(((Comparable) dest[j]).compareTo(dest[j+1]) > 0){
// ? ? ? ? swap(dest, j, j+1);?
// ? ? ? ? }
// ? ? }
// ? ? }
? ? //排序方法二：這是起泡排序的一種變體（小數上浮）
? ? for (int i = low; i < high; i++){
? ? for (int j = i; j > low ; j--){
? ? if(((Comparable) dest[j - 1]).compareTo(dest[j]) > 0){
? ? swap(dest, j-1, j);?
? ? }
? ? }
? ? }
? ? return;
? ? }
? ?
? ? int mid = (high + low)/2; //拆分
? ? mergeSort(dest, src, low, mid); //遞歸，可能會繼續拆分(那么必然繼續合并)
? ? mergeSort(dest, src, mid, high);
? ?
? ? //開始歸并,方法一
// ? ? for(int i=low,p=low,q=mid;i<high;i++){
// ? ? //第一個條件時為了添加剩余的值
// if(q >= high || (p < mid &&((Comparable) src[p]).compareTo(src[q]) <= 0)){
// dest[i] = src[p++];
// }else{
// dest[i] = src[q++];
// }
// ? ? }
? ?
? ? //開始歸并，方法二
? ? int i = low;
? ? int p = low; //第一個列表指針
? ? int q = mid; ? ?//第二個列表指針
? ? while(p < mid && q <high){
? ? if(((Comparable) src[p]).compareTo(src[q]) <= 0){
? ? dest[i++] = src[p++];
? ? }else{
? ? dest[i++] = src[q++];
? ? }
? ? }
? ? //添加剩余的值
? ? while(p < mid && i<high){
? ? dest[i++] = src[p++];
? ? }
? ? while(q < high && i<high){
? ? dest[i++] = src[q++];
? ? }


? ? private static void swap(Object[] x, int a, int b) {
? ? Object t = x[a];
? ? x[a] = x[b];
? ? x[b] = t;
? ? }
}
轉自：http://zhouyunan2010.iteye.com/blog/1179483

總結

以上是生活随笔為你收集整理的java中的排序算法——归并排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。