1

嘿，我似乎在尝试在 10,000 个随机数的数组上实现一些 Java 快速排序代码时遇到问题。我有一个文本文件，其中包含放入数组中的数字，然后将其传递给排序算法进行排序。我的目标是计算排序需要多长时间，使用我拥有的计时循环增加每次排序的数字。但是由于某种原因，使用此代码给了我一个曲线图而不是直线。我知道时序循环和数组代码工作正常，所以排序代码似乎有问题，但似乎找不到任何东西！非常感谢任何帮助，谢谢！

import java.io.*;
import java.util.*;
public class Quicksort {

public static void main(String args[]) throws IOException {
//Import the random integer text file into an integer array
File fil = new File("randomASC.txt");
FileReader inputFil = new FileReader(fil);
int [] myarray = new int [10000];
Scanner in = new Scanner(inputFil);

for(int q = 0; q < myarray.length; q++)
{
  myarray[q] = in.nextInt();
}
in.close();



for (int n = 100; n < 10000; n += 100) { 
long total = 0;
for (int r = 0; r < 10; ++r) {  
  long start = System.nanoTime ();    
      quickSort(myarray,0,n-1);
      total += System.nanoTime() - start;
    }
  System.out.println (n + "," + (double)total / 10.0);
} 
}

 public static void quickSort(int[] a, int p, int r)
{
    if(p<r)
    {
        int q=partition(a,p,r);
        quickSort(a,p,q);
        quickSort(a,q+1,r);
    }
}

private static int partition(int[] a, int p, int r) {

    int x = a[p];
    int i = p-1 ;
    int j = r+1 ;

    while (true) {
        i++;
        while ( i< r && a[i] < x)
            i++;
        j--;
        while (j>p && a[j] > x)
            j--;

        if (i < j)
            swap(a, i, j);
        else
            return j;
    }
}

private static void swap(int[] a, int i, int j) {
    // TODO Auto-generated method stub
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}
}
4

1 回答 1

2

只有内部循环的第一次迭代实际上对您从文件中读取的数组进行排序。所有后续迭代都应用于已排序的数组。

但是由于某种原因，使用此代码给了我一个曲线图而不是直线。

如果您的意思是运行时间在 中非线性增长n，这是可以预料的，因为快速排序不是线性时间算法（没有比较排序）。

您的性能图看起来像一个很好的二次函数：

性能图

由于您选择了枢轴，您得到的是二次而不是O(n log(n))时间：因为大多数时候您在排序数组上调用您的函数，您选择枢轴的方法意味着您每次都遇到最坏的情况。

于 2012-12-08T13:22:56.033 回答