定时快速排序算法

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

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

，但是出于某种原因，使用这段代码得到的是一个曲线图，而不是直线。

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

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

​

​

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