Посмотрим на сортировку как на комбинаторную задачу. Просто переберём все возможные перестановки исходного массива, пока не найдём отсортированный вариант.
type
TAI = array of integer;
...
procedure PermutationSort(var A: TAI);
function IsSorted: boolean;
var
i: integer;
begin
result := true;
for i:= High(A)-1 downto 0 do
begin
if A[i] > A[i+1] then
begin
result := false;
break;
end;
end;
end;
function PermSort(Index: integer): boolean;
var
i: integer;
begin
if IsSorted then
result := true
else begin
result := false;
for i:= Index to High(A) do
begin
swap(A[Index], A[i]);
if PermSort(Index+1) then
begin
result := true;
Exit;
end;
swap(A[Index], A[i]);
end;
end;
end;
begin
PermSort(0);
end;
Сложность:
| Максимальная |
O(N·N!) |
| Минимальная |
O(N) |
| Средняя |
O(N·N!) |
