-2

我正在尝试在 MatLab 中实现快速排序。我有两个函数，一个将给定列表拆分为两个较小的列表，一个大于枢轴，一个小于枢轴。第二个函数递归调用快速排序并迭代到下一个较小的列表，再次调用快速排序。我的代码如下。当我用我的 300 个随机生成的数字列表运行代码时，我收到错误“内存不足。可能的原因是程序内的无限递归。”。

function [ less, pivot, greater ] = SplitList( list, pivotindex )
%List Splitting Function
%In order to preform quick sort you firts must be able to split the list 
%into two, one which is greater than, and one which is less than the pivot.

pivot = list(1,pivotindex);

greater = [];
less = [];

for l = 1:length(list)
    if list(1,l) > pivot
        greater = [greater list(1, l)];
    else if list(1,l) <= pivot
        less = [less list(1, l)];
        end
    end

end

end

function [ qs_list ] = quick_sort( list )
%Recursive Quick Sort
%   quick sort algorithm to sort a list of numbers

%set (0,'RecursionLimit',1000);
pivotindex = round(length(list)/2); %sets pivot at the median value of the array

if length(list) > 1
    [ less, pivot, greater ] = SplitList( list, pivotindex ); %calls the SplitList function
    qs_list = [quick_sort(less) pivot quick_sort(greater)]; %calls quick_sort within the function

else
    qs_list = list;

end
end
4

1 回答 1

1

您的列表每次递归调用都会增加一个元素。

我们看一下SplitList()：返回的less元素个数加上返回的元素greater个数就是参数的元素个数list。

但是，当您在 中递归地组装排序列表时quick_sort()，您会连接和less，与 相比，这会将大小增加一倍。greater pivotqs_listlist

组装步骤应该是这样的：

    qs_list = [quick_sort(less) quick_sort(greater)];

稍后编辑

快速排序的优势之一是它可以就地进行排序（即对未排序和排序列表使用相同的内存区域）。这样可以避免重复需要排序的元素。

这意味着：您应该返回list作为参数获得的相同变量。否则，每次调用都会消耗两倍的内存：未排序的listN 个元素和部分排序的列表的 N 个元素less和greater. 假设平均时间复杂度为 O(N×log(N))，您消耗的内存顺序为 O(2 N×log(N) ) = O(N×2 N )。难怪您的内存不足 300 个元素。

尝试SplitList像这样重写你的：

function list = SplitList(list, beginindex, endindex, pivotindex)
    ...

此外，您quick_sort需要以同样的方式重写。

于 2016-10-05T20:27:41.397 回答