如何在快速排序算法中计算比较

问：

我有一个快速排序的算法，我正在尝试计算其中的比较次数。它使用大小为 10、100、1000 和 10,000 的随机生成的数组，并且具有常量种子，因此每次都会在数组中生成相同的值。（因此，可以预先确定结果并进行比较以检查计数是否正确）。我得到的值是 13、147、1506 和 11014。我期待的是 25、630、10292 和 132882。

/**
 * @file quicksort.hpp
 */

#ifndef QUICKSORT_H
#define QUICKSORT_H

#include <algorithm>

static const int MIN_SIZE  = 10; // Smallest size of an array that quicksort will sort

/**
 * Sorts the items in an array into ascending order.
 * @pre  None.
 * @post  theArray is sorted into ascending order; n is unchanged.
 * @param theArray  The given array.
 * @param first  The first element to consider in theArray.
 * @param last  The last element to consider in theArray.
 * @return the number of comparisons
 */
template<class ItemType>
int insertionSort(ItemType theArray[], int first, int last) {
    int counter = 0;
    for (int unsorted = first + 1; unsorted <= last; unsorted++) {
        ItemType nextItem = theArray[unsorted];
        int loc = unsorted;
        while ((loc > first) && (counter++, theArray[loc - 1] > nextItem)) {
            
            theArray[loc] = theArray[loc - 1];
            loc--;
        }
        theArray[loc] = nextItem;
    }
    return counter;
}

/**
 * Arranges two specified array entries into sorted order by
 * exchanging them, if necessary.
 * @param theArray  The given array.
 * @param i  The index of the first entry to consider in theArray.
 * @param j  The index of the second entry to consider in theArray.
 * */
template<class ItemType>
void order(ItemType theArray[], int i, int j) {
    if (theArray[i] > theArray[j]) {
        std::swap(theArray[i], theArray[j]);
    }
}

/** 
 * Arranges the first, middle, and last entry in an array in sorted order.
 * @pre  theArray[first..last] is an array; first <= last.
 * @post  theArray[first..last] is is arranged so that its
 * first, middle, and last entries are in sorted order.
 * @param theArray  The given array.
 * @param first  The first entry to consider in theArray.
 * @param last  The last entry to consider in theArray.
 * @return  The index of the middle entry.
 */
template<class ItemType>
int sortFirstMiddleLast(ItemType theArray[], int first, int last) {
    int mid = first + (last - first) / 2;
    order(theArray, first, mid); // Make theArray[first] <= theArray[mid]
    order(theArray, mid, last);  // Make theArray[mid] <= theArray[last]
    order(theArray, first, mid); // Make theArray[first] <= theArray[mid]

    return mid;
}

/**
 * Partitions the entries in an array about a pivot entry for quicksort.
 * @pre  theArray[first..last] is an array; first <= last.
 * @post  theArray[first..last] is partitioned such that:
 * S1 = theArray[first..pivotIndex-1] <= pivot * theArray[pivotIndex] == pivot
 * S2 = theArray[pivotIndex+1..last]  >= pivot
 * @param theArray  The given array.
 * @param first  The first entry to consider in theArray.
 * @param last  The last entry to consider in theArray.
 * @return  The index of the pivot.
 */
template<class ItemType>
int partition(ItemType theArray[], int first, int last, int counter) {
    // Choose pivot using median-of-three selection
    int pivotIndex = sortFirstMiddleLast(theArray, first, last);

    // Reposition pivot so it is last in the array
    std::swap(theArray[pivotIndex], theArray[last - 1]);
    pivotIndex = last - 1;
    ItemType pivot = theArray[pivotIndex];

    // Determine the regions S1 and S2
    int indexFromLeft = first + 1;
    int indexFromRight = last - 2;

    bool done = false;
    while (!done) {
        // Locate first entry on left that is >= pivot
        
        while (counter++, theArray[indexFromLeft] < pivot) {
            
            indexFromLeft = indexFromLeft + 1;
        }
        
        // Locate first entry on right that is <= pivot
        while (counter++, theArray[indexFromRight] > pivot) {
            indexFromRight = indexFromRight - 1;
            
        }
    
        if (indexFromLeft < indexFromRight) {
            std::swap(theArray[indexFromLeft], theArray[indexFromRight]);
            indexFromLeft = indexFromLeft + 1;
            indexFromRight = indexFromRight - 1;
            
        }
        else {
            done = true;
        }
    }

    // Place pivot in proper position between S1 and S2, and mark its new location
    std::swap(theArray[pivotIndex], theArray[indexFromLeft]);
    pivotIndex = indexFromLeft;

    counter++;

    return pivotIndex;
}

/**
 * Sorts an array into ascending order. Uses the quick sort with
 * median-of-three pivot selection for arrays of at least MIN_SIZE
 * entries, and uses the insertion sort for other arrays.
 * @pre  theArray[first..last] is an array.
 * @post  theArray[first..last] is sorted.
 * @param theArray  The given array.
 * @param first  The first element to consider in theArray.
 * @param last  The last element to consider in theArray.
 * @return the number of comparisons
 */
template<class ItemType>
int quicksort(ItemType theArray[], int first, int last, int& counter) {
    
    if (last - first + 1 < MIN_SIZE) {
        counter += insertionSort(theArray, first, last);
    }
    else {
        // Create the partition: S1 | Pivot | S2
        int pivotIndex = partition(theArray, first, last, counter);

        // Sort subarrays S1 and S2
        quicksort(theArray, first, pivotIndex - 1, counter);
        quicksort(theArray, pivotIndex + 1, last, counter);
    }
    return counter; 
}

#endif

这是快速排序的代码。

std::cout << "Quicksort                               ";
    std::cout << "    " << std::left << quicksort(makeRandomArray(10, seed), 0, 10-1, comparisons);
    comparisons = 0;
    std::cout << "    " << quicksort(makeRandomArray(100, seed), 0, 100-1, comparisons);
    comparisons = 0;
    std::cout << "    " << quicksort(makeRandomArray(1000, seed), 0, 1000-1, comparisons);
    comparisons = 0;
    std::cout << "    " << quicksort(makeRandomArray(10000, seed), 0, 10000-1, comparisons) << std::endl;

这是 main.cpp 文件中用于打印快速排序比较的代码。我知道它既不漂亮也不高效，但就目前而言，它有效。我只想让我的快速排序计数准确无误。 编辑：数组生成器的代码：

int* makeRandomArray(int n, int seed) {
srand(seed);
int * a = new int[n];
for (int i = 0; i < n; i++) {
    a[i] = rand() % 1000;
}
return a;

}