algorithm - 没有数据类型的快速排序算法

Question

大多数快速排序的实现都是处理整数数组的排序。因此，在具有固定数据类型的语言(例如 Pascal)中，需要修改算法才能对其他数组(例如 strings 数组)进行排序。

这当然是一项简单的任务，除了在我们的数组假定采用的值集上实现顺序关系之外，只需要进行少量修改。但是，最好有一个放之四海而皆准的实现方案。

我的问题是:

Question: Is it possible to write a "Quicksort Pascal Unit" which could be used to sort any array, be it of integers, strings or whatever?

需要解决的主要困难是该单元将无法访问矩阵条目的数据类型。

Answer 1

提出问题通常会引发一个快速得出答案的心理过程，这是我刚刚找到的一个问题，我对此感到非常高兴。

要点是要认识到快速排序算法只需要知道矩阵条目的类型，以便:

• 比较，和
• 交换

他们。因此，如果您为执行这些任务提供替代方法，快速排序会很高兴。

为了做到这一点，声明了一个“函数类型”orderRel，它接受两个整数(被认为是要比较的矩阵条目的索引)和一个“过程类型” copierProc(也采用两个索引，意味着将一个矩阵条目复制到另一个矩阵条目。请参见下面的代码)。

然后根据这些子例程专门实现快速排序单元，而调用程序的任务是在完整 View 中实现 orderRel 和 copierProc数据类型，它显然知道。这两个子例程然后作为参数传递给快速排序。

这是快速排序单元的完整实现，您将在下面找到完整的测试程序。两者都在“Free Pascal Compiler version 3.0.4+dfsg-18ubuntu2 [2018/08/29] for x86_64”中进行了测试。

{$R+}

unit Quicksort;

interface

type
  orderRel = function(i, j: longint): boolean;                (* Order relation for sorting *)
  copierProc = procedure(i, j: longint);                      (* Used to copy matrix entry i to entry j *)

procedure qsort(n: longint; less: orderRel; cp: copierProc);  (* Quicksort takes two functions as arguments *)

implementation

procedure qsort(n: longint; less: orderRel; cp: copierProc);

  var left, rght: longint;

  procedure qsort1(a, b: longint);
  begin
  cp((a+b) div 2, n+1); (* Position n+1 of the matrix used as pivot *)
  left:= a; rght:= b;
  while left <= rght do begin
    while less(left, n+1) do inc(left);
    while less(n+1, rght) do dec(rght);
    if left <= rght then begin
      cp(left, n+2); cp(rght, left); cp(n+2, rght); (* Position n+2 used as auxiliar variable for swapping *)
      inc(left); dec(rght);
      end;
    end;
  if left < b then qsort1(left, b);
  if a < rght then qsort1(a, rght);
  end;

begin
qsort1(1,n);
end;

end.

这是测试程序:

program Test; (* For testing unit quicksort *)

uses quicksort;

const
  N = 9;

(* Matrices to be sorted.  One of integers, the other of strings *)

var
  int_arr:  array[1..N+2] of integer; (* Quicksort needs two extra working slots, hence N+2 *)
  st_arr:   array[1..N+2] of string;

(* Next two subroutines to be fed to Quicksort when sorting integer matrices *)

function int_comparisson (i, j: longint): boolean;
begin
int_comparisson:= int_arr[i] < int_arr[j];
end;

procedure int_copy(i, j: longint);
begin
int_arr[j]:= int_arr[i];
end;

(* Next two subroutines to be fed to Quicksort when sorting matrices of strings *)

function st_comparisson(i, j: longint): boolean;
begin
st_comparisson:= st_arr[i] < st_arr[j];
end;

procedure st_copy(i, j: longint);
begin
st_arr[j]:= st_arr[i];
end;

var
  i: integer;

begin

(* Initialize integer matrix *)
for i:= 1 to N do int_arr[i]:= random(100);

qsort(N, @int_comparisson, @int_copy); (* Quicksort takes two functions as arguments *)

for i:= 1 to N do write(int_arr[i]:5);
writeln;

(* Initialize matrix of strings *)
st_arr[1]:= 'the';
st_arr[2]:= 'quick';
st_arr[3]:= 'brown';
st_arr[4]:= 'fox';
st_arr[5]:= 'jumps';
st_arr[6]:= 'over';
st_arr[7]:= 'the';
st_arr[8]:= 'lazy';
st_arr[9]:= 'dog';

qsort(N, @st_comparisson, @st_copy);

for i:= 1 to N do write(st_arr[i], ' '); writeln;

end.

PS:quicksort其实除了比较和交换，还需要存储一个枢轴，它显然必须具有与另一个相同的类型矩阵条目。而不是提供一个额外的变量来发挥作用枢轴的，这将不可避免地要求矩阵类型是显示，解决方案是允许快速排序访问一个未使用的矩阵条目，比如条目 n+1。然后使用另一个条目，即 n+2交换的辅助变量。