快速排序算法比较次数统计结果与预期不符问题排查

我实现了结合三数取中（median-of-three） pivot选择与插入排序优化的快速排序算法，尝试统计排序过程中的比较次数。使用固定种子生成大小为10、100、1000、10000的随机数组，确保每次数组元素一致以便验证计数准确性。当前得到的比较次数为13、147、1506、11014，但预期结果应为25、630、10292、132882。

相关代码 #

quicksort.hpp #

/**
 * @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;

随机数组生成代码 #

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;
}

错误排查与修正 #

你的计数逻辑存在多处遗漏和错误，导致统计结果远低于预期，具体问题和修复方案如下：

1. partition函数计数器传递方式错误 #

当前partition的counter是按值传递，函数内的累加不会影响外部的引用变量，必须改为引用传递：

// 修改前
int partition(ItemType theArray[], int first, int last, int counter) {
// 修改后
int partition(ItemType theArray[], int first, int last, int& counter) {
}

2. sortFirstMiddleLast中的比较未计数 #

order函数中的元素比较是快速排序的一部分，但完全未被统计。需要修改order函数并传递计数器引用：

// 修改后的order函数
template<class ItemType>
void order(ItemType theArray[], int i, int j, int& counter) {
    counter++; // 统计本次比较
    if (theArray[i] > theArray[j]) {
        std::swap(theArray[i], theArray[j]);
    }
}

// 修改后的sortFirstMiddleLast函数
template<class ItemType>
int sortFirstMiddleLast(ItemType theArray[], int first, int last, int& counter) {
    int mid = first + (last - first) / 2;
    order(theArray, first, mid, counter);
    order(theArray, mid, last, counter);
    order(theArray, first, mid, counter);

    return mid;
}

同时在partition中调用sortFirstMiddleLast时传入counter：

int pivotIndex = sortFirstMiddleLast(theArray, first, last, counter);

3. partition末尾的多余计数 #

partition最后一行的counter++;没有对应的比较操作，属于无效计数，直接删除。

4. 插入排序的计数逻辑遗漏边界比较 #

原插入排序的循环条件仅在loc > first为真时才计数，会漏掉部分元素比较。修改为明确计数每一次元素对比：

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++;
            if (theArray[loc - 1] > nextItem) {
                theArray[loc] = theArray[loc - 1];
                loc--;
            } else {
                break;
            }
        }
        theArray[loc] = nextItem;
    }
    return counter;
}

内容的提问来源于stack exchange，提问作者imnapr