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 - 我真的写了一个合并排序算法吗？

回答

相关问题