数组栈实现Hoare快速排序报错修复及实现错误排查

我尝试基于数组实现栈结构，并为其实现采用Hoare分区方案的快速排序，但代码运行异常，在执行mid = arr[(left + right) / 2]; N_op += 4;语句时抛出异常，其中N_op为操作计数变量。需要定位该报错的修复方法，同时排查实现中存在的其他错误。

原实现代码如下：

#include <ctime>
#include <iostream>
#include <windows.h>
const int MAX_SIZE = 3000;

using namespace std;

template <typename T>
class Stack
{
public:
    T* arr;
    int size;
    unsigned long long int N_op;

    Stack()
    {
        arr = new T[MAX_SIZE];
        size = 0;
    }

    void Push(int x)
    {
        arr[size++] = x;
        N_op += 5;
    }

    void Pop()   
    {
        size--;
        N_op += 2;
    }

    T Top() 
    {
        N_op += 3;
        return arr[size - 1];
    }

    T Size()
    {
        N_op++;
        return size;
    }

    void Sort(int N)
    {
        int mid, left, right, l, r;
        mid = left = right = l = r = 0; N_op += 6;

        Push(N - 1); N_op += 2;
        Push(0); N_op++;

        do {
            left = Top(); N_op += 2;
            Pop(); N_op++;
            right = Top(); N_op += 2;
            Pop(); N_op++;
            {
                mid = arr[(left + right) / 2]; N_op += 4;
                l = left; N_op++;
                r = right; N_op++;
                while (l < r) 
                {
                    N_op++;

                    while (arr[l] < mid) 
                    {
                        l++;
                        N_op += 4;
                    }
                    while (mid < arr[r])
                    {
                        r--;
                        N_op += 4;
                    }

                    if (l <= r)
                    {
                        swap(arr[l], arr[r]);
                        l++;
                        r--;
                        N_op += 9;
                    }
                }
            }

            if (left < r)
            {
                Push(r);
                Push(left);
                N_op += 3;
            }

            if (l < right)
            {
                Push(right);
                Push(l);
                N_op += 3;
            }
        }
        while (Size() != -1);
    }
};

int main()
{
    setlocale(LC_ALL, "Rus");
    srand(time(NULL));

    int i, t_s, t_f;

    int Key[3000];
    int N = 300;
    Stack<int> stack;

    for (i = 0; i < 3000; i++)
        Key[i] = rand() % 999;

    for (i = 0; i < 10; i++)
    {
        for (int z = N - 300; z < N; z++)
            stack.Push(Key[z]);

        stack.N_op = 0;
        t_s = GetTickCount64();
        stack.Sort(N);
        t_f = GetTickCount64();

        cout << "Номер сортировки: " << i + 1 << " | Количество отсортированных элементов: " << N << " | Время сортировки (ms): " << t_f - t_s << " | Количество операций (N_op): " << stack.N_op << endl;
        N += 300;
    }
}

执行到取mid值语句报错的核心原因是数组下标越界，由栈循环终止条件错误导致：

• 排序逻辑用栈模拟递归快排的区间存储，所有区间处理完成后栈为空，此时size = 0。但代码写的循环终止条件是while (Size() != -1)，空栈时size为0永远不满足终止条件，循环会继续执行。
• 空栈状态下调用Top()会访问arr[size - 1] = arr[-1]，读取到栈外的垃圾值作为left、right参数，后续计算(left + right)/2会得到远超0~2999范围的非法下标，访问arr[非法下标]直接触发内存访问异常。
• 修复方法：将Sort函数do-while循环的终止条件改为while (Size() != 0)，栈空时直接退出排序循环。

• 构造函数未初始化计数变量：Stack构造函数仅初始化了arr和size，N_op是未赋值的垃圾值，首次运行时操作计数结果完全错误，还可能触发未定义行为。需要在构造函数中添加N_op = 0;。
• 模板类方法参数类型写死：Stack是泛型模板类，但Push方法的形参固定为int x，如果实例化非int类型的栈会出现类型不匹配错误。需要将Push参数改为T x。
• 栈操作无边界校验：Pop、Top方法没有判断栈是否为空，空栈时调用Pop会把size减为负数，调用Top会访问负下标，都会触发越界。需要在两个方法开头添加空栈判断，空栈时直接返回（Pop）或抛出异常/返回默认值（Top）。
• Size方法返回值类型错误：size成员本身是int类型，但Size方法定义的返回值为模板类型T，非int实例化时会出现无意义的类型转换。需要将Size的返回值类型改为int。
• 测试逻辑未重置栈状态：main函数的多轮测试中，每轮N递增300后直接往栈里push新元素，没有清空上一轮排序后栈内留存的旧元素，栈内实际元素数量和传入Sort的N值不匹配，排序会读写不属于当前测试集的旧数据。需要在每轮测试push新元素前，将栈的size重置为0。
• 存在内存泄漏：类中用new申请的堆内存arr没有对应释放，会在程序退出前造成内存泄漏。需要给Stack添加析构函数，执行delete[] arr;释放内存。

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