排序陣列

Question

我有多個陣列，它們都開始整場，從1到5場，而這些都是像需要從分排序，到最大指標：

TArrayA = record 
      Field1:integer; 
      Field2:integer; 
      Field3:integer; 
      Field4:integer; 
      Field5:integer; 
      ... //other fields, strings, integers... up to 50 fields 
     end; 

    ArrayA:=array of TArrrayA; 

目前我使用這種方法來進行排序：

// sort by Field1 
    top:=Length(ArrayA); 
     for counter := 0 to top do 
     begin 
      min := counter; 
      for look := counter + 1 to top do 
      if ArrayA[look].Field1 < ArrayA[min].Field1 then 
       min := look; 
      vTmpRecord := ArrayA[min]; 
      ArrayA[min] := ArrayA[counter]; 
      ArrayA[counter] := vTmpRecord; 
     end; 

    // now sort by Field2 
    top:=Length(ArrayA); 
     for counter := 0 to top do 
     begin 
      min := counter; 
      for look := counter + 1 to top do 
      if (ArrayA[look].Field1 = ArrayA[min].Field1) And 
       (ArrayA[look].Field2 < ArrayA[min].Field2) then 
       min := look; 
      vTmpRecord := ArrayA[min]; 
      ArrayA[min] := ArrayA[counter]; 
      ArrayA[counter] := vTmpRecord; 
     end; 

這做這項工作。雖然有點慢，當我需要排序所有5個字段， ，這是我如何做，逐場，所以我排序數組5次。 有沒有更好，更快的方法？

這裏是例子：

procedure TForm1.Button8Click(Sender: TObject); 
type 
    TArrayA = record 
    Field1: integer; 
    Field2: integer; 
    Field3: integer; 
    Field4: integer; 
    Field5: integer; 
    end; 
var 
    ArrayA: array of TArrayA; 
    vTmpRecord: TArrayA; 
    top, counter, min, max, look: integer; 
    i,t1,t2:integer; 
begin 

    SetLength(ArrayA,100000); 
    for i := 0 to 99999 do 
    begin 
    ArrayA[i].Field1:=1+Random(100); 
    ArrayA[i].Field2:=1+Random(100); 
    ArrayA[i].Field3:=1+Random(100); 
    ArrayA[i].Field4:=1+Random(100); 
    ArrayA[i].Field5:=1+Random(100); 
    end; 


    t1:=GetTickCount; 
    // sort by Field1 
    top := Length(ArrayA); 
    for counter := 0 to top do 
    begin 
    min := counter; 
    for look := counter + 1 to top do 
     if ArrayA[look].Field1 < ArrayA[min].Field1 then 
     min := look; 
    vTmpRecord := ArrayA[min]; 
    ArrayA[min] := ArrayA[counter]; 
    ArrayA[counter] := vTmpRecord; 
    end; 

    // sort by Field2 
    top := Length(ArrayA); 
    for counter := 0 to top do 
    begin 
    min := counter; 
    for look := counter + 1 to top do 
     if (ArrayA[look].Field1 = ArrayA[min].Field1) and 
     (ArrayA[look].Field2 < ArrayA[min].Field2) then 
     min := look; 
    vTmpRecord := ArrayA[min]; 
    ArrayA[min] := ArrayA[counter]; 
    ArrayA[counter] := vTmpRecord; 
    end; 

    // sort by Field3 
    top := Length(ArrayA); 
    for counter := 0 to top do 
    begin 
    min := counter; 
    for look := counter + 1 to top do 
     if (ArrayA[look].Field1 = ArrayA[min].Field1) and (ArrayA[look].Field2 = ArrayA[min].Field2) and 
     (ArrayA[look].Field3 < ArrayA[min].Field3) then 
     min := look; 
    vTmpRecord := ArrayA[min]; 
    ArrayA[min] := ArrayA[counter]; 
    ArrayA[counter] := vTmpRecord; 
    end; 

    // sort by Field4 
    top := Length(ArrayA); 
    for counter := 0 to top do 
    begin 
    min := counter; 
    for look := counter + 1 to top do 
     if (ArrayA[look].Field1 = ArrayA[min].Field1) and (ArrayA[look].Field2 = ArrayA[min].Field2) and (ArrayA[look].Field3 = ArrayA[min].Field3) and 
     (ArrayA[look].Field4 < ArrayA[min].Field4) then 
     min := look; 
    vTmpRecord := ArrayA[min]; 
    ArrayA[min] := ArrayA[counter]; 
    ArrayA[counter] := vTmpRecord; 
    end; 

    // sort by Field5 
    top := Length(ArrayA); 
    for counter := 0 to top do 
    begin 
    min := counter; 
    for look := counter + 1 to top do 
     if (ArrayA[look].Field1 = ArrayA[min].Field1) and (ArrayA[look].Field2 = ArrayA[min].Field2) and (ArrayA[look].Field3 = ArrayA[min].Field3) and (ArrayA[look].Field4 = ArrayA[min].Field4) and 
     (ArrayA[look].Field5 < ArrayA[min].Field5) then 
     min := look; 
    vTmpRecord := ArrayA[min]; 
    ArrayA[min] := ArrayA[counter]; 
    ArrayA[counter] := vTmpRecord; 
    end; 

    t2:=GetTickCount; 
    Button8.Caption:=IntToStr(t2-t1); 
end; 

Answer 1

您要做的最重要的事情是將排序算法與數據分開。這樣，您可以使用不同數據一次又一次地編寫或使用單一排序算法。

執行此操作的經典方法是使用比較排序。它們是需要比較兩個項目的比較函數的排序算法，並且返回小於的負整數，大於的正整數和等於的零。

因此，讓我們開始爲您的數據展示這樣一個比較函數。因爲存儲了多個字段，所以很難編寫通用比較器。最好將這些字段放入數組中。一旦你這樣做，你可以做使用迭代這樣比較lexicographically：

function CompareIntegerArray(const lhs, rhs: array of Integer): Integer; 
var 
    i: Integer; 
begin 
    Assert(Length(lhs) = Length(rhs)); 
    for i := low(lhs) to high(lhs) do 
    if lhs[i] < rhs[i] then 
     exit(-1) 
    else if lhs[i] > rhs[i] then 
     exit(1); 

    exit(0); 
end; 

有了字典順序，我們首先比較的主要領域。如果它們不同，我們會得到我們的答案，否則我們會轉到二級領域。等等。如上所示，這種算法非常適合迭代。

這可以克服您的方法中的一個重大缺陷，只需對陣列進行一次排序即可。

一旦你有了這個比較函數，你需要將它包裝在一個外部比較函數中，該函數從記錄字段中提取數據並填充數組。也許，沿着這些線路：

type 
    TMyArray = array [1..5] of Integer; 

function GetMyArray(const Value: TArrayA): TMyArray; 
begin 
    Result[1] := Value.Field1; 
    Result[2] := Value.Field2; 
    .... 
end; 

function MyCompare(const lhs, rhs: TArrayA): Integer; 
begin 
    Result := CompareIntegerArray(
    GetMyArray(lhs), 
    GetMyArray(rhs) 
); 
end; 

如今如許，你可以使用這個功能比較與通用有點像TArray.Sort<T>從Generics.Collections。這是一個Quicksort的實現，這是一個平均複雜度爲O（n log n）的比較排序。這通常會比您的O（）bubble sort產生巨大的收益。

如果您可以用實際數組替換記錄，生活會更簡單。另一個可能有用的選擇是向記錄中添加一個方法，該方法返回一個整數數組，可以在詞典比較函數中使用。

總括：

1. 獨立數據，比較和排序，以方便重複利用和清晰度。
2. 使用數組來使字典對比可以用循環實現。
3. 使用高效排序算法，如Quicksort。

Answer 2

您可以使用內置的快速排序的方法與您的自定義比較排序數組：

uses 
    System.Math, 
    System.Generics.Defaults, 
    System.Generics.Collections; 

    TArray.Sort<TArrayA>(ArrayA, TComparer<TArrayA>.Construct(function(const Left, Right: TArrayA): Integer 
    begin 
    if Left.Field1 = Right.Field1 then 
     begin 
     if Left.Field2 = Right.Field2 then 
      begin 
      Result := CompareValue(Left.Field3, Right.Field3); 
      end 
     else Result := CompareValue(Left.Field2, Right.Field2); 
     end 
    else Result := CompareValue(Left.Field1, Right.Field1); 
    end 
)); 

我只對前三個字段添加的代碼，但你將得到圖片如何建立你自己的比較器的更多領域。