Лучший способ сортировки массива
https://stackoverflow.com/questions/41733
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Допустим, у меня есть массив записей, которые я хочу отсортировать на основе одного из полей в записи.Каков наилучший способ достичь этого?
TExample = record
SortOrder : integer;
SomethingElse : string;
end;
var SomeVar : array of TExample;
Решение
Вы можете добавить указатели на элементы массива в TList, затем позвоните TList.Sort с помощью функции сравнения и, наконец, создайте новый массив и скопируйте значения из списка T в нужном порядке.
Однако, если вы используете следующую версию, 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));
Другие советы
(Я знаю, что это год спустя, но все еще полезный материал.)
Предложение Скамрадта дополнить целочисленные значения предполагает, что вы собираетесь выполнять сортировку с помощью сравнения строк.Это было бы медленно.Вызываю format() для каждой вставки, еще медленнее.Вместо этого вы хотите выполнить сравнение целых чисел.
Вы начинаете с типа записи:
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;
Обратите внимание на трюк с приведением целочисленного сортировщика к указателю TObject, который хранится в свойстве TStringList.Object .(Это зависит от того факта, что целое число и указатель имеют одинаковый размер.) Где-то мы должны определить функцию для сравнения указателей 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 по .Объекту, вызвав .CustomSort вместо .Sort (который будет сортировать по строковому значению.)
tsExample.CustomSort(@CompareObjects); //Sort the list
TStringList теперь отсортирован, так что вы можете выполнить итерацию по нему от 0 до .Count-1 и прочитать строки в отсортированном порядке.
Но предположим, вам нужен не TStringList, а просто массив в отсортированном порядке.Или записи содержат больше данных, чем просто одна строка в этом примере, и ваш порядок сортировки более сложный.Вы можете пропустить шаг добавления каждой строки и просто добавить индекс массива в виде элементов в 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 посоветовали сделать в своих ответах.
Если вам нужна сортировка по строке, то используйте sorted TStringList и
добавить запись с помощью TString.AddObject(string, Pointer(int_val)).
Но если нужна сортировка по целочисленному полю и строке - используйте TObjectList и после добавления всех записей вызовите TObjectList.Sort с необходимыми отсортированными функциями в качестве параметра.
Все это зависит от количества записей, которые вы сортируете.Если вы сортируете меньше нескольких сотен, то другие методы сортировки работают нормально, если же вы собираетесь сортировать больше, то внимательно присмотритесь к старому надежному Turbo Power Системные инструменты проект.В исходный код включен очень хороший алгоритм сортировки.Тот, который очень хорошо справляется с эффективной сортировкой миллионов записей.
Если вы собираетесь использовать метод TStringList для сортировки списка записей, убедитесь, что ваше целое число дополнено справа, прежде чем вставлять его в список.Вы можете использовать формат ('%.10d',[rec.sortorder]) например, выровнять по правому краю до 10 цифр.
Алгоритм быстрой сортировки часто используется, когда требуется быстрая сортировка.Delphi использует (или была) его для списка.Например, сортировка.Delphi List можно использовать для сортировки чего угодно, но это тяжеловесный контейнер, который должен выглядеть как массив указателей на структуры.Это тяжеловесно, даже если мы используем трюки, подобные Гаю Гордону в этом потоке (помещаем индекс или что-либо еще вместо указателей или вводим непосредственно значения, если они меньше 32 бит):нам нужно составить список и так далее...
Следовательно, альтернативой простой и быстрой сортировке массива struct может быть использование функция выполнения qsort C от msvcrt.dll.
Вот объявление, которое может быть хорошим (Предупреждение:переносимый код только для Windows).
type TComparatorFunction = function(lpItem1: Pointer; lpItem2: Pointer): Integer; cdecl;
procedure qsort(base: Pointer; num: Cardinal; size: Cardinal; lpComparatorFunction: TComparatorFunction) cdecl; external 'msvcrt.dll';
Полный пример здесь.
Обратите внимание, что непосредственная сортировка массива записей может быть медленной, если записи большие.В этом случае сортировка массива указателей на записи может быть более быстрой (что-то вроде подхода со списком).
С массивом я бы использовал либо quicksort или, возможно heapsort, и просто измените сравнение , чтобы использовать TExample.SortOrder, часть подкачки по-прежнему будет просто воздействовать на массив и менять местами указатели.Если массив очень большой, то вам может понадобиться структура связанного списка, если происходит много вставок и удалений.
Процедуры, основанные на C, здесь есть несколько http://www.yendor.com/programming/sort/
Другой сайт, но с исходным кодом на паскале http://www.dcc.uchile.cl /~rbaeza/handbook/sort_a.html
Используйте один из алгоритмов сортировки, предложенных Википедия.Функция 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;
