java – 为什么我的quicksort性能比我的mergesort差?

前端之家收集整理的这篇文章主要介绍了java – 为什么我的quicksort性能比我的mergesort差?前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
我错过了什么吗?来源很短,随时可以运行和评论,以便更好地理解.我需要知道我做错了什么.
  1. package com.company;
  2.  
  3. import java.io.BufferedReader;
  4. import java.io.FileReader;
  5. import java.io.IOException;
  6. import java.util.*;
  7.  
  8. public class Main {
  9.  
  10. public static ArrayList<Integer> randomArrayList(int n)
  11. {
  12. ArrayList<Integer> list = new ArrayList<>();
  13. Random random = new Random();
  14.  
  15. for (int i = 0; i < n; i++)
  16. {
  17. list.add(random.nextInt(n));
  18. }
  19. return list;
  20. }
  21.  
  22. public static List<Integer> MergeSort(List<Integer> A) throws Exception{
  23.  
  24. if (A.size()==1)
  25. return A;
  26.  
  27. int mid = A.size()/2;
  28.  
  29. List<Integer> left = A.subList(0,mid);
  30. List<Integer> right = A.subList(mid,A.size());
  31.  
  32. left = MergeSort(left);
  33. right = MergeSort(right);
  34. A = Merge(left,right);
  35.  
  36. return A;
  37. }
  38.  
  39. public static List<Integer> Merge(List<Integer> L,List<Integer> R) throws Exception{
  40.  
  41. List<Integer> output = new ArrayList<Integer>(Collections.nCopies(L.size() + R.size(),0));
  42.  
  43. int i = 0; int j = 0; int k = 0;
  44. while (i < L.size() && j < R.size()) {
  45. if (L.get(i) < R.get(j)) {
  46. output.set(k,L.get(i));
  47. i=i+1;
  48. }
  49. else {
  50. output.set(k,R.get(j));
  51. j=j+1;
  52. }
  53. k++;
  54. }
  55. while (i < L.size()) {
  56. output.set(k,L.get(i));
  57. i=i+1;
  58. k++;
  59. }
  60. while (j < R.size()) {
  61. output.set(k,R.get(j));
  62. j=j+1;
  63. k++;
  64. }
  65.  
  66. return output;
  67. }
  68.  
  69. public static List<Integer> QuickSort(List<Integer> A) throws Exception{
  70.  
  71. if (A.size()==1 || A.size()==0)
  72. return A;
  73.  
  74. //The pivot is a random element of the array A
  75. int randomIndex = new Random().nextInt(A.size());
  76. Integer P = A.get(randomIndex);
  77.  
  78. //Swap first element of A with selected pivot
  79. Integer tmp;
  80. A.set(randomIndex,A.get(0));
  81. A.set(0,P);
  82.  
  83. //Initiate i and l (partition analysis progress counters)
  84. int l = 0,i = l + 1,r = A.size();
  85.  
  86.  
  87. for (int j = l + 1; j < r; j++ ){
  88. if (A.get(j)< P ){
  89. //Swap A[j] and A[i]
  90. tmp = A.get(j);
  91. A.set(j,A.get(i));
  92. A.set(i,tmp);
  93. //Increase i by 1 (counting the pos of already partitioned)
  94. i = i + 1;
  95. }
  96. }
  97.  
  98. //Swap A[l] (Pivot) and A[i-1] most left element bigger than pivot
  99. tmp = A.get(l);
  100. A.set(l,A.get(i-1));
  101. A.set(i - 1,tmp);
  102.  
  103. QuickSort(A.subList(0,i-1));
  104. QuickSort(A.subList(i,A.size()));
  105.  
  106. return A;
  107. }

在main函数中,我运行20次两种方法进行比较.您可以复制代码的两个部分并运行它

  1. public static void main(String[] args) throws Exception{
  2.  
  3. long startTime,endTime,duration;
  4.  
  5. //Compare 20 times QuickSort vs MergeSort
  6. for (int i=0;i<20;i++){
  7.  
  8. List<Integer> arreglo = randomArrayList(100000);
  9.  
  10. startTime = System.nanoTime();
  11. QuickSort(arreglo);
  12. endTime = System.nanoTime();
  13.  
  14. duration = (endTime - startTime)/1000000;
  15. System.out.println("Quicksort: " + Long.toString(duration));
  16.  
  17. startTime = System.nanoTime();
  18. MergeSort(arreglo);
  19. endTime = System.nanoTime();
  20.  
  21. duration = (endTime - startTime)/1000000;
  22. System.out.println("MergeSort: "+Long.toString(duration));
  23.  
  24. //System.out.println(Arrays.toString(QuickSort(arreglo).toArray()));
  25. //System.out.println(Arrays.toString(MergeSort(arreglo).toArray()));
  26. }
  27. }
  28. }

解决方法

这是我的评论作为答案:您正在对同一列表进行两次排序,因此第二种排序总是对已经排序的列表进行排序(这几乎总是与第一次排序的列表不同).

试试你的主要代码的这个变种:

  1. public static void main(String[] args) throws Exception{
  2.  
  3. long startTime,duration;
  4.  
  5. //Compare 20 times QuickSort vs MergeSort
  6. for (int i=0;i<20;i++){
  7.  
  8. List<Integer> arreglo = randomArrayList(100000);
  9. List<Integer> arreglo2 = new ArrayList<>(arreglo); // Make a copy
  10.  
  11. startTime = System.nanoTime();
  12. QuickSort(arreglo); // Sort the original
  13. endTime = System.nanoTime();
  14.  
  15. duration = (endTime - startTime)/1000000;
  16. System.out.println("Quicksort: " + Long.toString(duration));
  17.  
  18. startTime = System.nanoTime();
  19. MergeSort(arreglo2); // Sort the copy
  20. endTime = System.nanoTime();
  21.  
  22. duration = (endTime - startTime)/1000000;
  23. System.out.println("MergeSort: "+Long.toString(duration));
  24. }
  25. }

猜你在找的Java相关文章