2

我需要帮助调试快速排序。当我调试时，它实际上对数组进行了正确排序，但在最后几个步骤中，它最终会进行不必要的交换并最终返回一个未排序的数组。我花了很长时间试图找出导致它的原因，但我没有取得任何进展。

我选择了分区作为第一个元素（我知道这不是最佳的，但我只是想了解 QS）。

脚本： 

A = [3 6 2 5 1 7 4];
rightIndex = length(A);
E = QuickSort(A,1,rightIndex);

快速排序：

function [pvt, B] = QuickSort(A,left,right)

if left < right
    [B, pvt] = PartnPivot1(A, left, right); %chosen pivot
    QuickSort(B, left, pvt-1); 
    QuickSort(B, pvt+1, right);
end

分割：

function [sortedSubArray, pivot] = PartnPivot1(subArray,leftIndex,rightIndex)

%% Initializations
S = subArray;
left = leftIndex;
right = rightIndex;

P = S(left); %pivot
i = left+1;

%% Partition
for j = i:right
    if S(j) < P 
            temp1 = S(j); %
            temp2 = S(i); % swap S(i) with S(j) 
            S(j) = temp2; %
            S(i) = temp1; %
            i = i+1; %increment i only when swap occurs
    end
end
swap1 = S(left); %
swap2 = S(i-1);  % final swap 
S(left) = swap2; %
S(i-1) = swap1;  %

sortedSubArray = S;
pivot = P;
4

1 回答 1

1

对 QuickSort 的递归调用需要将输出分配给一些变量，否则排序后的数组永远不会被传回。我也认为您不需要返回枢轴。

我在浏览器中输入而不是在 Matlab 中进行测试，但我认为这会做到......

function A = QuickSort(A,left,right)

if left < right
    [A, pvt] = PartnPivot1(A, left, right); %chosen pivot
    A = QuickSort(A, left, pvt-1); 
    A = QuickSort(A, pvt+1, right);
end
于 2013-02-24T04:41:51.550 回答