Java - 我真的寫了一個合併排序算法嗎？

幸運的是，它非常快，我可以在20秒內對15,000,000個元素進行排序（當然，這取決於本地CPU的速度）。

我已經看過「實際」合併排序實現的源代碼，它們都沒有看起來像我的代碼。該算法應該或多或少是相同的（我認爲）。它使用一個幫助器方法，將兩個已排序的列表組合成一個組合的排序列表。然後，MergeSort方法遞歸地將未排序的列表分解成兩半，直到它到達一個元素大小的列表，然後將它們組合起來，因爲它用前面所述的幫助器方法結束堆棧。

import java.util.*; 

public class MergeSort{ 

    public static void main(String []args){ 
     List a = fillListRand(150); 
     List sorted = mergeSort(a); 
     System.out.println("Done."); 
     System.out.println("Unsorted: " + a.toString()); 
     System.out.println("Sorted: " + sorted.toString()); 
    } 

    public static List mergeSort(List unsorted) { 
     if(unsorted.size() == 1) 
      return unsorted; 

     return mergeLists(mergeSort(unsorted.subList(0,unsorted.size()/2)), 
          mergeSort(unsorted.subList(unsorted.size()/2,unsorted.size()))); 
    } 

    public static List mergeLists(List a, List b) { 
     List newList = new ArrayList(); 
     int aIndex = 0; 
     int bIndex = 0; 

     while((aIndex < a.size()) && (bIndex < b.size())) { 
      if((int)a.get(aIndex) > (int)b.get(bIndex)) { 
       newList.add(b.get(bIndex)); 
       bIndex++; 
      } 

      else { 
       newList.add(a.get(aIndex)); 
       aIndex++; 
      } 
     } 

     if(aIndex >= a.size()) 
      newList.addAll(b.subList(bIndex,b.size())); 

     else if (bIndex >= b.size()) 
      newList.addAll(a.subList(aIndex,a.size())); 

     return newList; 
    } 

    public static List fillListRand(int num) { 
     List newList = new ArrayList(); 
     Random r = new Random(); 
     for(int i = 0; i < num; i++) { 
      newList.add(r.nextInt(100)); 
     } 
     return newList; 
    } 
}

謝謝！

來源

2014-09-19 David Parker

究竟是如此不同。此外，這是否工作;如你所見，是否有任何理由/收穫，如果你改變了它？ – ChiefTwoPencils 2014-09-19 22:21:26

除此之外，您不必檢查最後索引的大小。你可以''同時'轉儲剩餘的元素。無論如何，支票都會發生。 – ChiefTwoPencils 2014-09-19 22:24:17

是的，它對我的目的非常有效。但我想知道是否創建了一個Merge Sort的偏差/變體，它可能不像Time或Space高效。 – 2014-09-19 22:24:44

是的，這是一種合併排序，只要它將元素大致分爲兩半，然後對每一半進行排序併合並。運行時間爲O（n log n），額外的空間使用量爲O（n）。您提到的主要區別在於其他合併排序實現通常具有左側，中間和右側索引。您隱藏了撥打.subList的索引算法，這可以說是更優雅，但可能效率更低，具體取決於.subList的實現方式。如果log n重複調用.subList會導致一連串的log n對象，那麼每個元素訪問將耗費O（log n）時間，因爲它在鏈中穿行。幸運的是，每個元素只能以這種方式訪問一次，所以漸近總運行時間將從O（n log n）保持不變。（使用.subList構造的列表上調用.subList似乎更有可能使中間對象不起作用，因此指針深度將保持爲O（1）。）

來源

2014-09-19 22:48:39

謝謝你的回答，這就是我所希望的。 – 2014-09-19 22:52:53

Java - 我真的寫了一個合併排序算法嗎？

回答

相關問題