java - 时序快速排序算法

Question

嘿，我在尝试对 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;
}
}

Answer 1

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

But for some reason using this code gives me a curved graph instead of a straight linear line.

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

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

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