2

我必须通过每次将数组的大小增加 100 来对快速排序执行运行时分析。但是，当我使用 System.nanoTime 测量运行时间时，结果与我预期的不同（我的图表看起来更像 O(2^n)）。每当数组达到 800 左右时，时间就会增加。有人可以告诉我我的代码哪里出错了。

计数部分目前也有点无关紧要，因为我只想在每个数组大小处运行一次快速排序。

import java.util.Random;


public class Quickworking {

public static void main(String[] args) {
    Random rand = new Random();
    int count2;
    long total = 0;
    count2 = 1;
    int [] myArray = new int[1400];   

                //generates random array
    for (int i = 0; i < myArray.length; i++){
        myArray[i] = rand.nextInt(100) + 1;
        //System.out.print(myArray[i] + ", ");
    }

            //loop sort n amount of times
    for (int count = 0; count < count2; count++){

            //calls the sort method on myArray giving the arguments
        long start = System.nanoTime();
        sort( myArray, 0, myArray.length - 1 );
        long end = System.nanoTime();
        System.out.println(end - start );
        total += (end - start);
    }
    //long average = (long) total / (long) count2;

    //System.out.println(average);


    //prints the sorted array
    //for (int i = 0; i <myArray.length; i++){
    //  System.out.print(myArray[i] + ", ");
    //}

}

public static int sort(int myArray[], int left, int right){
    int i = left, j = right;
    int temp;
    int pivot = myArray[(left + right) / 2];
    //System.out.println("here are the pivot numbers " + pivot + ", ");


    if (i <= j){

        while (myArray[i] < pivot) //&& (i<right))  
            i++;
        while (myArray[j] > pivot) //&& (j>left))  
            j--;
        if (i <= j){
            temp = myArray[i];
            myArray[i] = myArray[j];
            myArray[j] = temp;
            i++;
            j--;


        }
    } 

    if (left < j) sort(myArray, left, j);
    if (i < right) sort(myArray, i, right);

    return i;

}
}
4

2 回答 2

2

对已排序的数组进行排序时，快速排序的行为是 O(n^2)。在您的代码中第一次对数组进行排序后，您将对排序后的数组进行排序。这将为您提供快速排序的最坏情况。您每次都需要生成一个全新的随机数组来真正测试它。

于 2012-12-08T16:18:37.917 回答
1

QuickSort 在已经排序的数据上表现不佳。见这里： http ://en.wikipedia.org/wiki/Quicksort

您应该在 for 循环中随机化您的数组以获得更准确的结果。

于 2012-12-08T16:22:47.923 回答