将 HeapSort 和 ShellSort 从 C 转换为 Pascal
Converting HeapSort and ShellSort from C to Pascal
我有两种排序的问题 — 堆和 Shell。我在 C 中有一些代码,我需要尝试在程序主体中使用相同的命令(就像我在 C 中使用 'for-loop' 时一样,我也想对 Pascal 使用 'for-loop') .我尝试了,但是排序不像在 C 中那样工作。在 C 中,所有这些都适用于大小为 40000 的数组。
Shell在 C 中排序的代码,其中参数 'n' 是数组的大小:
shellSort(int n){
int shift,pom,j,i;
shift = n/2;
while(shifta>0){
for (i = shift; i < n; i += 1){
pom=arr[i];
j=i;
while((j>=shift) && (arr[j-shift]>pom)){
arr[j] = arr[j - shift];
j=j-shift;
}
arr[j]=pom;
}
shift= shift / 2;
}
}
Pascal 声明
arr :array[0..22] of integer;
size:integer =23;
具有相同参数的 Pascal 代码:
procedure ShellSort(n:integer);
Var
shift , pom : Integer;
Begin
shift:=n div 2 ;
While shift>0 Do
Begin
For i:=shift to n Do
Begin
pom:=arr[i];
j:=i;
While (j>=shift) and (arr[j-shift]>pom) Do
Begin
arr[j]:=arr[j-shift];
j:= j-shift
End;
arr[j]:=pom;
End;
shift:=shift div 2;
End;
End;
C 中的堆排序代码:
heapSort() {
int N = size;
int k;
int pom;
for (k = N / 2; k > 0; k--) {
downHeap(k, N);
}
do {
pom = arr[0];
arr[0] = arr[N - 1];
arr[N - 1] = pom;
N = N - 1;
downHeap(1, N);
} while (N > 1);
}
downHeap(int k, int N) {
int T = arr[k - 1];
while (k <= N / 2) {
int j = k + k;
if ((j < N) && (arr[j - 1] < arr[j])) {
j++;
}
if (T >= arr[j - 1]) {
break;
} else {
arr[k - 1] = arr[j - 1];
k = j;
}
}
arr[k - 1] = T;
}
Pascal 中的堆排序代码:
procedure downHeap(k:integer;N:integer);
var
T:integer;
begin
T:=arr[k-1];
while(k<= (N div 2)) do
begin
j:=k+k;
if ((j<N) and (arr[j-1]<arr[j])) then
begin
j:=j+1;
end;
if (T>=arr[j-1]) then
begin
exit;
end
else
begin
arr[k-1]:=arr[j-1];
k:=j;
end;
end;
arr[k-1]:=T;
end;
procedure heapSort;
var
n, pom:integer;
begin
n:=size;
for i:=n div 2 downto 1 do
begin
downHeap(i,n);
end;
repeat
begin
pom:=arr[0];
arr[0]:=arr[n-1];
arr[n-1]:=pom;
n:=n-1;
downHeap(1,n);
end;
until n>1;
end;
Pascal 的输出:
Unsorted array
10 9 8 7 6 5 4 3 3 2 1 0 15 15 15 15 14 18 99 1 19 95 95
BubbleSort
0 1 1 2 3 3 4 5 6 7 8 9 10 14 15 15 15 15 18 19 95 95 99
HeapSort
95 95 15 18 95 15 15 15 18 19 95 0 5 4 15 3 14 7 3 1 2 1 99
ShellSort
0 0 1 1 2 3 3 4 5 7 14 15 15 15 15 15 18 18 19 95 95 95 95
Expected
0 1 1 2 3 3 4 5 6 7 8 9 10 14 15 15 15 15 18 19 95 95 99
我真的很郁闷
正在将评论转为答案。
在Shell排序中,C循环为:
for (i = shift; i < n; i += 1){
Pascal 循环是
For i:=shift to n Do
Pascal 循环太频繁了;它必须是:
For i := shift to n-1 Do
假设循环限制中允许使用表达式——如果不允许,则需要一个额外的变量,大致如下:
var ub: integer;
ub := n - 1;
For i := shift to ub Do
C for 循环比 Pascal for 循环更通用、更灵活。
在堆排序中,C循环是:
do { … } while (N > 1);
并且您已将其翻译成
repeat … until n > 1;
终止条件错误; until
等同于while not
,所以你需要:
repeat … until n <= 1;
我从来没有仔细检查过整个 Pascal 代码——而且我没有 Pascal 编译器可以测试——所以可能还有其他问题需要解决,但这两个应该让你继续。 (确保您已检查所有出现的 for
和 repeat … until
是否存在此处列出的问题。)
我有两种排序的问题 — 堆和 Shell。我在 C 中有一些代码,我需要尝试在程序主体中使用相同的命令(就像我在 C 中使用 'for-loop' 时一样,我也想对 Pascal 使用 'for-loop') .我尝试了,但是排序不像在 C 中那样工作。在 C 中,所有这些都适用于大小为 40000 的数组。
Shell在 C 中排序的代码,其中参数 'n' 是数组的大小:
shellSort(int n){
int shift,pom,j,i;
shift = n/2;
while(shifta>0){
for (i = shift; i < n; i += 1){
pom=arr[i];
j=i;
while((j>=shift) && (arr[j-shift]>pom)){
arr[j] = arr[j - shift];
j=j-shift;
}
arr[j]=pom;
}
shift= shift / 2;
}
}
Pascal 声明
arr :array[0..22] of integer;
size:integer =23;
具有相同参数的 Pascal 代码:
procedure ShellSort(n:integer);
Var
shift , pom : Integer;
Begin
shift:=n div 2 ;
While shift>0 Do
Begin
For i:=shift to n Do
Begin
pom:=arr[i];
j:=i;
While (j>=shift) and (arr[j-shift]>pom) Do
Begin
arr[j]:=arr[j-shift];
j:= j-shift
End;
arr[j]:=pom;
End;
shift:=shift div 2;
End;
End;
C 中的堆排序代码:
heapSort() {
int N = size;
int k;
int pom;
for (k = N / 2; k > 0; k--) {
downHeap(k, N);
}
do {
pom = arr[0];
arr[0] = arr[N - 1];
arr[N - 1] = pom;
N = N - 1;
downHeap(1, N);
} while (N > 1);
}
downHeap(int k, int N) {
int T = arr[k - 1];
while (k <= N / 2) {
int j = k + k;
if ((j < N) && (arr[j - 1] < arr[j])) {
j++;
}
if (T >= arr[j - 1]) {
break;
} else {
arr[k - 1] = arr[j - 1];
k = j;
}
}
arr[k - 1] = T;
}
Pascal 中的堆排序代码:
procedure downHeap(k:integer;N:integer);
var
T:integer;
begin
T:=arr[k-1];
while(k<= (N div 2)) do
begin
j:=k+k;
if ((j<N) and (arr[j-1]<arr[j])) then
begin
j:=j+1;
end;
if (T>=arr[j-1]) then
begin
exit;
end
else
begin
arr[k-1]:=arr[j-1];
k:=j;
end;
end;
arr[k-1]:=T;
end;
procedure heapSort;
var
n, pom:integer;
begin
n:=size;
for i:=n div 2 downto 1 do
begin
downHeap(i,n);
end;
repeat
begin
pom:=arr[0];
arr[0]:=arr[n-1];
arr[n-1]:=pom;
n:=n-1;
downHeap(1,n);
end;
until n>1;
end;
Pascal 的输出:
Unsorted array
10 9 8 7 6 5 4 3 3 2 1 0 15 15 15 15 14 18 99 1 19 95 95
BubbleSort
0 1 1 2 3 3 4 5 6 7 8 9 10 14 15 15 15 15 18 19 95 95 99
HeapSort
95 95 15 18 95 15 15 15 18 19 95 0 5 4 15 3 14 7 3 1 2 1 99
ShellSort
0 0 1 1 2 3 3 4 5 7 14 15 15 15 15 15 18 18 19 95 95 95 95
Expected
0 1 1 2 3 3 4 5 6 7 8 9 10 14 15 15 15 15 18 19 95 95 99
我真的很郁闷
正在将评论转为答案。
在Shell排序中,C循环为:
for (i = shift; i < n; i += 1){
Pascal 循环是
For i:=shift to n Do
Pascal 循环太频繁了;它必须是:
For i := shift to n-1 Do
假设循环限制中允许使用表达式——如果不允许,则需要一个额外的变量,大致如下:
var ub: integer;
ub := n - 1;
For i := shift to ub Do
C for 循环比 Pascal for 循环更通用、更灵活。
在堆排序中,C循环是:
do { … } while (N > 1);
并且您已将其翻译成
repeat … until n > 1;
终止条件错误; until
等同于while not
,所以你需要:
repeat … until n <= 1;
我从来没有仔细检查过整个 Pascal 代码——而且我没有 Pascal 编译器可以测试——所以可能还有其他问题需要解决,但这两个应该让你继续。 (确保您已检查所有出现的 for
和 repeat … until
是否存在此处列出的问题。)