runtime - 为什么我的快速排序在 O(2^n)

Question

我必须通过每次将数组的大小增加 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;

}
}

Answer 1

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