在 scilab 中合并排序
Merge sort in scilab
我在 scilab 中使用以下代码实现了合并排序:
function x = mergesortre (x)
n = length (x);
if ( n > 1 ) then
m = floor (n/2);
p = n-m;
x1 = mergesortre ( x(1:m) );
x2 = mergesortre ( x(m+1:n) );
x = merge ( x1 , x2 );
end
endfunction
function [x] = merge ( x1 , x2 )
n1 = length (x1);
n2 = length (x2);
n = n1 + n2;
x = [];
i = 1
j = 1
k = 1
while(j<=n1 && k<=n2)
if x1(j)>=x2(k)
x(i)=x2(k);
k=k+1;
i=i+1;
elseif x1(j)<x2(k)
x(i)=x1(j);
j=j+1;
i=i+1;
end
end
if (j > n1) then
x(i+1:n) = x2(k:n2);
else
x(i+1:n) = x1(j:n1);
end
endfunction
a=[5,4,3,2,1];
x=mergesortre(a);
disp x;
然而,当我尝试使用终端 window 查看排序后的数组时,它只显示第一个元素,例如,如果我的数组是 [5,4,3,2,1] 它唯一给出输出为 1。我需要帮助来理解我做错了什么。
递归算法需要终止条件。你的函数mergesortre
中没有这样的条件。这可能是因为您的函数声明未使用输入参数 x
。尝试像这样更改它:
function [a] = mergesortre ( a )
我猜您想使用 a
作为输入和输出参数。
您的错误在 merge
函数中。由于 i
已经在循环结束时递增,因此您必须从 i
:
开始连接
if (j > n1) then
x(i:n) = x2(k:n2);
else
x(i:n) = x1(j:n1);
end
我在 scilab 中使用以下代码实现了合并排序:
function x = mergesortre (x)
n = length (x);
if ( n > 1 ) then
m = floor (n/2);
p = n-m;
x1 = mergesortre ( x(1:m) );
x2 = mergesortre ( x(m+1:n) );
x = merge ( x1 , x2 );
end
endfunction
function [x] = merge ( x1 , x2 )
n1 = length (x1);
n2 = length (x2);
n = n1 + n2;
x = [];
i = 1
j = 1
k = 1
while(j<=n1 && k<=n2)
if x1(j)>=x2(k)
x(i)=x2(k);
k=k+1;
i=i+1;
elseif x1(j)<x2(k)
x(i)=x1(j);
j=j+1;
i=i+1;
end
end
if (j > n1) then
x(i+1:n) = x2(k:n2);
else
x(i+1:n) = x1(j:n1);
end
endfunction
a=[5,4,3,2,1];
x=mergesortre(a);
disp x;
然而,当我尝试使用终端 window 查看排序后的数组时,它只显示第一个元素,例如,如果我的数组是 [5,4,3,2,1] 它唯一给出输出为 1。我需要帮助来理解我做错了什么。
递归算法需要终止条件。你的函数mergesortre
中没有这样的条件。这可能是因为您的函数声明未使用输入参数 x
。尝试像这样更改它:
function [a] = mergesortre ( a )
我猜您想使用 a
作为输入和输出参数。
您的错误在 merge
函数中。由于 i
已经在循环结束时递增,因此您必须从 i
:
if (j > n1) then
x(i:n) = x2(k:n2);
else
x(i:n) = x1(j:n1);
end