我错过了什么吗?来源很短,随时可以运行和评论,以便更好地理解.我需要知道我做错了什么.
- package com.company;
- import java.io.BufferedReader;
- import java.io.FileReader;
- import java.io.IOException;
- import java.util.*;
- public class Main {
- public static ArrayList<Integer> randomArrayList(int n)
- {
- ArrayList<Integer> list = new ArrayList<>();
- Random random = new Random();
- for (int i = 0; i < n; i++)
- {
- list.add(random.nextInt(n));
- }
- return list;
- }
- public static List<Integer> MergeSort(List<Integer> A) throws Exception{
- if (A.size()==1)
- return A;
- int mid = A.size()/2;
- List<Integer> left = A.subList(0,mid);
- List<Integer> right = A.subList(mid,A.size());
- left = MergeSort(left);
- right = MergeSort(right);
- A = Merge(left,right);
- return A;
- }
- public static List<Integer> Merge(List<Integer> L,List<Integer> R) throws Exception{
- List<Integer> output = new ArrayList<Integer>(Collections.nCopies(L.size() + R.size(),0));
- int i = 0; int j = 0; int k = 0;
- while (i < L.size() && j < R.size()) {
- if (L.get(i) < R.get(j)) {
- output.set(k,L.get(i));
- i=i+1;
- }
- else {
- output.set(k,R.get(j));
- j=j+1;
- }
- k++;
- }
- while (i < L.size()) {
- output.set(k,L.get(i));
- i=i+1;
- k++;
- }
- while (j < R.size()) {
- output.set(k,R.get(j));
- j=j+1;
- k++;
- }
- return output;
- }
- public static List<Integer> QuickSort(List<Integer> A) throws Exception{
- if (A.size()==1 || A.size()==0)
- return A;
- //The pivot is a random element of the array A
- int randomIndex = new Random().nextInt(A.size());
- Integer P = A.get(randomIndex);
- //Swap first element of A with selected pivot
- Integer tmp;
- A.set(randomIndex,A.get(0));
- A.set(0,P);
- //Initiate i and l (partition analysis progress counters)
- int l = 0,i = l + 1,r = A.size();
- for (int j = l + 1; j < r; j++ ){
- if (A.get(j)< P ){
- //Swap A[j] and A[i]
- tmp = A.get(j);
- A.set(j,A.get(i));
- A.set(i,tmp);
- //Increase i by 1 (counting the pos of already partitioned)
- i = i + 1;
- }
- }
- //Swap A[l] (Pivot) and A[i-1] most left element bigger than pivot
- tmp = A.get(l);
- A.set(l,A.get(i-1));
- A.set(i - 1,tmp);
- QuickSort(A.subList(0,i-1));
- QuickSort(A.subList(i,A.size()));
- return A;
- }
在main函数中,我运行20次两种方法进行比较.您可以复制代码的两个部分并运行它
- public static void main(String[] args) throws Exception{
- long startTime,endTime,duration;
- //Compare 20 times QuickSort vs MergeSort
- for (int i=0;i<20;i++){
- List<Integer> arreglo = randomArrayList(100000);
- startTime = System.nanoTime();
- QuickSort(arreglo);
- endTime = System.nanoTime();
- duration = (endTime - startTime)/1000000;
- System.out.println("Quicksort: " + Long.toString(duration));
- startTime = System.nanoTime();
- MergeSort(arreglo);
- endTime = System.nanoTime();
- duration = (endTime - startTime)/1000000;
- System.out.println("MergeSort: "+Long.toString(duration));
- //System.out.println(Arrays.toString(QuickSort(arreglo).toArray()));
- //System.out.println(Arrays.toString(MergeSort(arreglo).toArray()));
- }
- }
- }
解决方法
这是我的评论作为答案:您正在对同一列表进行两次排序,因此第二种排序总是对已经排序的列表进行排序(这几乎总是与第一次排序的列表不同).
试试你的主要代码的这个变种:
- public static void main(String[] args) throws Exception{
- long startTime,duration;
- //Compare 20 times QuickSort vs MergeSort
- for (int i=0;i<20;i++){
- List<Integer> arreglo = randomArrayList(100000);
- List<Integer> arreglo2 = new ArrayList<>(arreglo); // Make a copy
- startTime = System.nanoTime();
- QuickSort(arreglo); // Sort the original
- endTime = System.nanoTime();
- duration = (endTime - startTime)/1000000;
- System.out.println("Quicksort: " + Long.toString(duration));
- startTime = System.nanoTime();
- MergeSort(arreglo2); // Sort the copy
- endTime = System.nanoTime();
- duration = (endTime - startTime)/1000000;
- System.out.println("MergeSort: "+Long.toString(duration));
- }
- }