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 中，要根据枢轴对数组进行分区，您在尝试确定其正确位置时 包括枢轴本身。

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

两种解决方案：

解决方案 1：

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
    % ...

解决方案 2：

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
    % ...

Answer 2

我在这里深入探讨了如何优化您对 MATLAB 的使用、您应该如何更好地利用递归函数和重新起草代码。 要跳到快速排序函数的工作重写，请参阅下面的第 2^nd 和第 4^th 个代码块

在您的函数中使用 low 和 high 索引来跟踪您的分区并没有帮助。使用递归快速排序函数的全部要点是：

从数组 ar

ar(p)

拆分为 2 个数组，一个值小于 ar(p)，一个值大于 ar(p)。相等的值可以放在任一数组中，因为它们将保留在枢轴旁边。
Return 到第 1 步。对每个列表重复。

列表是自相似的，我的意思是将每个子列表视为需要排序的自己的列表，而不是更大列表的一部分！您不需要跟踪索引（当您深入 3 个递归时，索引最终会造成混淆），只需单独分析每个列表。

您可能会发现 Wikipedia article 很有用，因为它详细说明了这 3 点，并建议了一些最佳选择枢轴的方案。在下面的代码中，我只选择了中间的元素。

此外，您的分区函数 parti 确实效率低下。在 MATLAB 中，如果您发现自己循环遍历数组的每个索引，那么您可能会加快速度。相反，使用逻辑索引向量化您的代码！

至少，在 documentation 中了解更多关于索引的知识，因为您可以像这样做整洁的事情：

% Your code for swapping array elements
tmp = arr(i);
ar(i) = ar(r);
ar(r) = tmp;
% Using MATLAB's indexing
ar([i,r]) = ar([r,i]);

编辑：虽然这展示了一种更 "MATLAB-esque" 的做事方式，you incur a performance hit assigning elements like this，所以如果您不介意更长的代码，请随意使用临时工！

您可以用这个 7 行函数替换所有代码，这样会更快。我添加了评论来解释逻辑...

function ar = qs(ar)
% Quicksort algorithm, for some 1D array "ar"
% First check we have more than one element, vital to terminate the recursion!
    if numel(ar) > 1
        % Choose some pivot index p, which we will split the array around
        p = ceil(numel(ar)/2);
        % Put values from "ar" which are smaller than "ar(p)" in one array
        smaller = ar(ar < ar(p));
        % Put values from "ar" which are larger than "ar(p)" in another array
        larger = ar(ar > ar(p));
        % Rebuild "ar" from a (qs-sorted) array of the smaller elemenets, then all
        % elements which were equal the pivot element (no need to sort these!) then 
        % a (qs-sorted) array of the larger elements.
        ar = [qs(smaller), ar(ar == ar(p)), qs(larger)];    
    end
end

这可以是运行，如您的测试所示：

ar = [7,7,3,0,3,1,4,7,5,6];
qs(ar)
>> ans = [0 1 3 3 4 5 6 7 7 7]

我们可以通过不显式声明 smaller 和 larger 以及始终选择 p=1（尽管对于已经排序的数组来说这是最坏的情况）来使它更短。

function ar = qs(ar)
    if numel(ar) > 1
        ar = [qs(ar(ar < ar(1))), ar(ar == ar(1)), qs(ar(ar > ar(1)))];    
    end
end

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

QuickSort program reaching maximum recursion limit of 500?

sorting

algorithm

recursion

matlab

quicksort

两种解决方案：

解决方案 1：

解决方案 2：