algorithm - QuickSort 程序达到最大递归限制 500？

Question

我正在通过在 MATLAB 中绘制图形来分析排序算法。下面是我的快速排序代码。当我运行它时出现此错误:

Maximum recursion limit of 500 reached. Use set(0,'RecursionLimit', N) to change the limit. Be aware that exceeding your available stack space can crash MATLAB and/or your computer. Error in ==> quickSort

为什么会出现这个错误？我的代码有什么问题吗？

function [ar] = quickSort(ar, low, high)
    if low < high
        [ar, q] = parti(ar, low, high);
        ar = quickSort(ar, low, q - 1);
        ar = quickSort(ar, q + 1, high);
    end
end

function [ar, i] = parti(ar, p, r)
    x = ar(r);
    i = p - 1;

    for j = p : r
        if ar(j) <= x
            i = i + 1;
            if i ~= j
                tmp = ar(i);
                ar(i) = ar(j);
                ar(j) = tmp;
            end
        end
    end
    i = i + 1;
    tmp = ar(i);
    ar(i) = ar(r);
    ar(r) = tmp;
end

我正在调用这个函数使用

ar = [7,7,3,0,3,1,4,7,5,6]
quickSort(ar, 1, 10)

Answer 1

在函数 parti 中，要根据枢轴对数组进行分区，您在尝试确定其正确位置时包括枢轴本身。

在某些情况下，这会导致无限递归，因为 pivot 只是在相邻位置之间交换，因为它与自身进行比较。

两种解决方案:

解决方案一:

function [ar,i]= parti(ar,p,r)
    x=ar(r);
    i=p-1;

    for j=p:r-1 % Notice the r-1
        if ar(j) <= x
            i=i+1;
            if i~=j
    % ...

方案二:

function [ar,i]= parti(ar,p,r)
    x=ar(r);
    i=p-1;

    for j=p:r
        if ar(j) < x % Notice the change in checking
            i=i+1;
            if i~=j
    % ...