免責事項：これは、コードとアルゴリズムの説明が必要な質問です。何かを修正したり最適化したりすることを意図したものではなく、理解を容易にすることを目的としています。
ソートルーチンについての私の理解はあまりよくありません。integer typeマージソート用にすでに利用可能なコードをここからここに変換するための助けを求めましstring typeた：文字列配列用のdelphiマージソート。答えを受け取った後、私はソートルーチンを理解するために着手しました。
理解を助けるために、いくつかのリソースが役に立ちました。
- http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/merge/mergen.htm
- http://www.youtube.com/watch?v=9Qk1t66g7IU
私はそれに従うためにコードを分析しようとしました。この質問は、マージソートについての私自身の理解を検証するための私の試みではなく、ソートルーチンを明確に示しています。この質問の価値は、マージソートをよりよく理解しようとする人々にとってです。1つのプロトタイプをよく理解すれば、他の種類のことも理解しやすくなるため、これは不可欠です。
私の質問は、なぜ「1」を追加して長さを設定し、「結果」に追加したのかということです。
SetLength(AVals, Length(Vals) div 2 + 1);
Result := 1 + PerformMergeSort(0, High(Vals));
ここでなぜ「1」を引いたのですか？ 編集：1を引いていない場合、Kは範囲外になると思いますか？
Result := k - 1;
これがこの質問のコードです。ところで、これは配列の半分しかコピーしないため、最適化されたマージソートです。
function MergeSortRemoveDuplicates(var Vals: array of Integer):Integer;
var
AVals: array of Integer;
//returns index of the last valid element
function Merge(I0, I1, J0, J1: Integer):Integer;
var
i, j, k, LC:Integer;
begin
LC := I1 - I0;
for i := 0 to LC do
AVals[i]:=Vals[i + I0];
//copy lower half or Vals into temporary array AVals
k := I0;
i := 0;
j := J0;
while ((i <= LC) and (j <= J1)) do
if (AVals[i] < Vals[j]) then begin
Vals[k] := AVals[i];
inc(i);
inc(k);
end else if (AVals[i] > Vals[j]) then begin
Vals[k]:=Vals[j];
inc(k);
inc(j);
end else begin //duplicate
Vals[k] := AVals[i];
inc(i);
inc(j);
inc(k);
end;
//copy the rest
while i <= LC do begin
Vals[k] := AVals[i];
inc(i);
inc(k);
end;
if k <> j then
while j <= J1 do begin
Vals[k]:=Vals[j];
inc(k);
inc(j);
end;
Result := k - 1;
end;
//returns index of the last valid element
function PerformMergeSort(ALo, AHi:Integer): Integer; //returns
var
AMid, I1, J1:Integer;
begin
//It would be wise to use Insertion Sort when (AHi - ALo) is small (about 32-100)
if (ALo < AHi) then
begin
AMid:=(ALo + AHi) shr 1;
I1 := PerformMergeSort(ALo, AMid);
J1 := PerformMergeSort(AMid + 1, AHi);
Result := Merge(ALo, I1, AMid + 1, J1);
end else
Result := ALo;
end;
begin
SetLength(AVals, Length(Vals) div 2 + 1);
Result := 1 + PerformMergeSort(0, High(Vals));
end;
これが私の理解ですが、非常に小さな変更が加えられています。
function MergeSortRemoveDuplicates(var Vals: array of Integer):Integer;
var
AVals: array of Integer;
//returns index of the last valid element
function Merge(I0, I1, J0, J1: Integer):Integer;
var
i, j, k, LC:Integer;
begin
// difference between mid-point on leftside
// between low(Original_array) and midpoint(true Original_array midpoint)
// subtracting I0 which is Low(Original_array)
// or here equals zero(0)
// so LC is quarter point in Original_array??
LC := I1 - I0;
// here we walk from begining of array
// and copy the elements between zero and LC
// this is funny call that Vals[i + I0] like 0 + 0
// then 1 + 0 and so on. I guess this guarantees if we are
// starting from non-zero based array??
for i := 0 to LC do
AVals[i]:=Vals[i + I0];
// k equal low(Original_array)
k := I0;
// I will be our zero based counter element
i := 0;
// J will be (midpoint + 1) or
// begining element of right side of array
j := J0;
// while we look at Copy_array elements
// between first element (low(Copy_array)
// and original_array from midpoint + 1 to high(Original_array)
// we start to sort it
while ((i <= LC) and (j <= J1)) do
// if the value at Copy_array is smaller than the Original_array
// we move it to begining of Original_array
// remember position K is first element
if (AVals[i] < Vals[j]) then begin
Vals[k] := AVals[i];
// move to next element in Copy_array
inc(i);
// move to next element in Original_array
inc(k);
// if the value at copy_array is larger
// then we move smaller value from J Original_array (J is midpoint+1)
// to position K original_array (K now is the lower part of ) Original_array)
end else if (AVals[i] > Vals[j]) then begin
Vals[k]:=Vals[j];
//move K to the next element in Original_array
inc(k);
// move j to next element in Original_array
inc(j);
// if the value in Original_array is equal to the element in Copy_array
// do nothing and count everything up
// so we end up with one copy from duplicate and disregard the rest
end else begin //duplicate
Vals[k] := AVals[i];
inc(i);
inc(j);
inc(k);
end;
//copy the rest
while i <= LC do begin
Vals[k] := AVals[i];
inc(i);
inc(k);
end;
// if the counters do not endup at the same element
// this means we have some that maybe leftover on
// the right side of the Original_array.
// This explains why K does not equal J : there are still elements left over
// then copy them to Original_array
// starting at position K.
if k <> j then
while j <= J1 do begin
Vals[k]:=Vals[j];
inc(k);
inc(j);
end;
// why K - 1?
// function needs result so return will be null if called
// I don't understand this part
Result := k - 1;
end;
//returns index of the last valid element
function PerformMergeSort(ALo, AHi:Integer): Integer; //returns
var
AMid, I1, J1:Integer;
begin
//It would be wise to use Insertion Sort when (AHi - ALo) is small (about 32-100)
if (ALo < AHi) then
begin
AMid:=(ALo + AHi) shr 1; // midpoint
I1 := PerformMergeSort(ALo, AMid); //recursive call I1 is a data point on the left
J1 := PerformMergeSort(AMid + 1, AHi); // recursive call I1 is a data point on the right
Result := Merge(ALo, I1, AMid + 1, J1);
end else
Result := ALo;
end;
begin
// test if array is even then we can split nicely down middle
if Length(Vals) mod 2 = 0 then
begin
SetLength(AVals, Length(Vals) shr 1);
Result := PerformMergeSort(0, High(Vals));
end
else
//array is odd let us add 1 to it and make it even
// shr 1 is essentially dividing by 2 but doing it on the bit level
begin
SetLength(AVals, (Length(Vals) + 1) shr 1);
Result := PerformMergeSort(0, High(Vals));
end;
end;