Лучший способ сортировки массива
Скажем, у меня есть массив записей, которые я хочу отсортировать на основе одного из полей в записи. Какой лучший способ достичь этого?
TExample = record
SortOrder : integer;
SomethingElse : string;
end;
var SomeVar : array of TExample;
10 ответов
Вы можете добавить указатели на элементы массива в TListзатем позвоните TList.Sort с функцией сравнения, и, наконец, создать новый массив и скопировать значения из TList в нужном порядке.
Однако, если вы используете следующую версию, D2009, есть новая библиотека коллекций, которая может сортировать массивы. Требуется дополнительный IComparer<TExample> реализация для пользовательских заказов сортировки. Вот это в действии для вашего конкретного случая:
TArray.Sort<TExample>(SomeVar , TDelegatedComparer<TExample>.Construct(
function(const Left, Right: TExample): Integer
begin
Result := TComparer<Integer>.Default.Compare(Left.SortOrder, Right.SortOrder);
end));
(Я знаю, что это год спустя, но все же полезные вещи.)
Предложение Скамрадта дополнить целочисленные значения предполагает, что вы собираетесь сортировать, используя сравнение строк. Это будет медленно. Вызов формата () для каждой вставки, еще медленнее. Вместо этого вы хотите сделать целочисленное сравнение.
Вы начинаете с типа записи:
TExample = record
SortOrder : integer;
SomethingElse : string;
end;
Вы не указали, как хранились записи или как вы хотели получить к ним доступ после сортировки. Итак, давайте предположим, что вы поместили их в динамический массив:
var MyDA Array of TExample;
...
SetLength(MyDA,NewSize); //allocate memory for the dynamic array
for i:=0 to NewSize-1 do begin //fill the array with records
MyDA[i].SortOrder := SomeInteger;
MyDA[i].SomethingElse := SomeString;
end;
Теперь вы хотите отсортировать этот массив по целочисленному значению SortOrder. Если вам нужен TStringList (так что вы можете использовать метод ts.Find), тогда вы должны добавить каждую строку в список и добавить SortOrder в качестве указателя. Затем сортируйте по указателю:
var tsExamples: TStringList; //declare it somewhere (global or local)
...
tsExamples := tStringList.create; //allocate it somewhere (and free it later!)
...
tsExamples.Clear; //now let's use it
tsExamples.sorted := False; //don't want to sort after every add
tsExamples.Capacity := High(MyDA)+1 //don't want to increase size with every add
//an empty dynamic array has High() = -1
for i:=0 to High(MyDA) do begin
tsExamples.AddObject(MyDA[i].SomethingElse,TObject(MyDA[i].SortOrder));
end;
Обратите внимание на хитрость приведения Integer SortOrder в указатель TObject, который хранится в свойстве TStringList.Object. (Это зависит от того, что Integer и Pointer имеют одинаковый размер.) Где-то мы должны определить функцию для сравнения указателей TObject:
function CompareObjects(ts:tStringList; Item1,Item2: integer): Integer;
var i,j: integer;
begin
Result := integer(ts.Objects[i]) - integer(ts.Objects[j];
end;
Теперь мы можем отсортировать tsList для.Object, вызвав.CustomSort вместо.Sort (который будет сортировать по строковому значению.)
tsExample.CustomSort(@CompareObjects); //Sort the list
TStringList теперь отсортирован, так что вы можете перебирать его от 0 до.Count-1 и читать строки в отсортированном порядке.
Но предположим, что вам не нужен TStringList, просто массив в отсортированном порядке. Или записи содержат больше данных, чем только одна строка в этом примере, и ваш порядок сортировки более сложный. Вы можете пропустить этап добавления каждой строки и просто добавить индекс массива как Items в TList. Сделайте все выше тем же способом, за исключением использования TList вместо TStringList:
var Mlist: TList; //a list of Pointers
...
for i:=0 to High(MyDA) do
Mlist.add(Pointer(i)); //cast the array index as a Pointer
Mlist.Sort(@CompareRecords); //using the compare function below
function CompareRecords(Item1, Item2: Integer): Integer;
var i,j: integer;
begin
i := integer(item1); //recover the index into MyDA
j := integer(item2); // and use it to access any field
Result := SomeFunctionOf(MyDA[i].SomeField) - SomeFunctionOf(MyDA[j].SomeField);
end;
Теперь, когда Mlist отсортирован, используйте его как справочную таблицу для доступа к массиву в отсортированном порядке:
for i:=0 to Mlist.Count-1 do begin
Something := MyDA[integer(Mlist[i])].SomeField;
end;
Когда я перебираю TList, мы возвращаем индексы массива в отсортированном порядке. Нам просто нужно привести их обратно к целым числам, поскольку TList считает их указателями.
Мне нравится делать это таким образом, но вы также можете поставить реальные указатели на элементы массива в TList, добавив адрес элемента массива вместо его индекса. Затем, чтобы использовать их, вы приведете их в качестве указателей на записи TExample. Это то, что Барри Келли и CoolMagic сказали сделать в своих ответах.
Если вам нужно отсортировать по строке, используйте отсортированный TStringList и добавить запись по TString.AddObject(string, Pointer(int_val)),
Но если нужно отсортировать по целому полю и строке - используйте TObjectList и после добавления всех записей звоните TObjectList.Sort с необходимыми отсортированными функциями в качестве параметра.
Все зависит от количества записей, которые вы сортируете. Если вы сортируете только несколько сотен, то другие методы сортировки работают нормально, если вы собираетесь сортировать больше, то внимательно посмотрите на старый надежный проект Turbo Power SysTools. В исходный код включен очень хороший алгоритм сортировки. Тот, который делает очень хорошую работу, эффективно сортируя миллионы записей.
Если вы собираетесь использовать метод tStringList для сортировки списка записей, убедитесь, что ваше целое число дополнено вправо, прежде чем вставлять его в список. Вы можете использовать формат ("%.10d",[rec.sortorder]) для выравнивания по правому краю, например, до 10 цифр.
Алгоритм быстрой сортировки часто используется, когда требуется быстрая сортировка. Delphi (или был) использует его для List.Sort например. Delphi List может использоваться для сортировки чего угодно, но это тяжелый контейнер, который должен выглядеть как массив указателей на структуры. Это тяжеловесно, даже если мы используем трюки типа Гая Гордона в этом потоке (размещение индекса или чего-либо вместо указателей или непосредственное размещение значений, если они меньше 32 бит): нам нужно создать список и так далее...
Следовательно, альтернативой для простой и быстрой сортировки массива структуры может быть использование функции времени выполнения qsort C из msvcrt.dll.
Вот объявление, которое может быть хорошим (Внимание: код переносится только на окнах).
type TComparatorFunction = function(lpItem1: Pointer; lpItem2: Pointer): Integer; cdecl;
procedure qsort(base: Pointer; num: Cardinal; size: Cardinal; lpComparatorFunction: TComparatorFunction) cdecl; external 'msvcrt.dll';
Полный пример здесь.
Обратите внимание, что прямая сортировка массива записей может быть медленной, если записи большие. В этом случае сортировка массива указателей на записи может быть быстрее (как в случае с подходом List).
С массивом я бы использовал либо quicksort или возможно heapsortи просто измените сравнение, чтобы использовать TExample.SortOrderчасть подкачки все еще будет действовать на массив и указатели подкачки. Если массив очень большой, то вам может потребоваться структура связанного списка, если много вставок и удалений.
Подпрограммы на основе C, здесь есть несколько http://www.yendor.com/programming/sort/
Еще один сайт, но есть источник на паскале http://www.dcc.uchile.cl/~rbaeza/handbook/sort_a.html
Используйте один из предложенных Wikipedia алгоритмов сортировки. Функция Swap должна менять местами элементы массива, используя временную переменную того же типа, что и элементы массива. Используйте стабильную сортировку, если вы хотите, чтобы записи с одинаковым целочисленным значением SortOrder оставались в том порядке, в котором они были на первом месте.
TStringList иметь эффективный метод сортировки.
Если вы хотите сортировать, используйте TStringList объект с Sorted Свойство True.
ПРИМЕЧАНИЕ. Для большей скорости добавляйте объекты в несортированные TStringList и в конце измените свойство на True.
ПРИМЕЧАНИЕ. Для сортировки по целочисленному полю преобразуйте в строку.
ПРИМЕЧАНИЕ. Если имеются повторяющиеся значения, этот метод не является допустимым.
С уважением.
Если у вас Delphi XE2 или новее, вы можете попробовать:
var
someVar: array of TExample;
list: TList<TExample>;
sortedVar: array of TExample;
begin
list := TList<TExample>.Create(someVar);
try
list.Sort;
sortedVar := list.ToArray;
finally
list.Free;
end;
end;
Я создал очень простой пример, который работает правильно, если поле сортировки является строкой.
Type
THuman = Class
Public
Name: String;
Age: Byte;
Constructor Create(Name: String; Age: Integer);
End;
Constructor THuman.Create(Name: String; Age: Integer);
Begin
Self.Name:= Name;
Self.Age:= Age;
End;
Procedure Test();
Var
Human: THuman;
Humans: Array Of THuman;
List: TStringList;
Begin
SetLength(Humans, 3);
Humans[0]:= THuman.Create('David', 41);
Humans[1]:= THuman.Create('Brian', 50);
Humans[2]:= THuman.Create('Alex', 20);
List:= TStringList.Create;
List.AddObject(Humans[0].Name, TObject(Humans[0]));
List.AddObject(Humans[1].Name, TObject(Humans[1]));
List.AddObject(Humans[2].Name, TObject(Humans[2]));
List.Sort;
Human:= THuman(List.Objects[0]);
Showmessage('The first person on the list is the human ' + Human.name + '!');
List.Free;
End;