时间戳

首页 > 解决方案 > 为快速排序 C++ 生成最坏的情况

c++ - 为快速排序 C++ 生成最坏的情况

问题描述

我需要为标准快速排序创建最差的测试用例：一个从 1 到 N 且具有给定大小的数组（N 可以从 1 到 70000）。关键元素是中间的那个。我写了一个递归函数，将最大的元素放在中间（因此算法必须将左边的每个元素与它进行比较），然后将数组分成两部分，将下一个最大的元素放在结果部分的中间。但是，我的代码并没有通过所有案例。这里可能有什么问题？

PS我的目标是让快速排序尽可能多地进行比较

#include <iostream>
#include <fstream>

using namespace std;

int antiqs(int* array, int start, int end, int maxElement, int* time){
    if(end - start < 2) {
        return maxElement - *time;
    }

    int middle = (start + end) / 2;
    array[middle] = maxElement - *time;
    *time = *time + 1;

    antiqs(array, start, middle - 1, maxElement, time);
    antiqs(array, middle + 1, end, maxElement, time);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;

    ifstream fileIn("antiqs.in.txt");
    fileIn >> n;
    fileIn.close();

    int array[n];
    for(int i = 0; i < n; i++){
        array[i] = 0;
    }

    int time = 0;
    int max = antiqs(array, 0, n-1, n, &time);

    ofstream fileOut("antiqs.out.txt");
    for(int i = 0; i < n; i++){
        if(array[i] == 0){
            array[i] = max;
            max = max - 1;
        }
        fileOut << array[i] << " ";
     }
    fileOut.close();
    return 0;
}

标签： c++quicksort

解决方案

生成一个偶数递增后奇数递减的模式。例如：

2 4 6 8 10 7 5 3 1

2 4 6 8 7 5 3 1
 
2 4 6 7 5 3 1

2 4 6 5 3 1

2 4 5 3 1

2 4 3 1

2 3 1

2 1

1

使用中间元素作为主元的 Lomuto 分区方案示例：

void QuickSort(int a[], int lo, int hi)
{
    while (lo < hi){
        std::swap(a[(lo+hi)/2], a[hi]); // use mid point for pivot
        int p = a[hi];
        int i = lo;                     // Lomuto partition
        for (int j = lo; j < hi; ++j){
            if (a[j] < p){
                std::swap(a[j], a[i]);
                ++i;
            }
        }
        std::swap(a[i], a[hi]);
        if(i - lo <= hi - i){           // recurse on smaller, loop on larger
            QuickSort(a, lo, i-1);
            lo = i+1;
        } else {
            QuickSort(a, i+1, hi);
            hi = i-1;
        }
    }
}

推荐阅读