exam6p311unit1.pas

对大批量数据排序

unit Exam6P311Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls, StrUtils;

type
  TexampleForm1 = class(TForm)
    Memo1: TMemo;
    Button1: TButton;
    Memo3: TMemo;
    Label1: TLabel;
    Label2: TLabel;
    Label3: TLabel;
    Edit1: TEdit;
    Edit2: TEdit;
    Label4: TLabel;
    CheckBox1: TCheckBox;
    Button2: TButton;
    procedure Button1Click(Sender: TObject);
    procedure FormCreate(Sender: TObject);
    procedure Button2Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

CONST
  ArrMaxLen=200000;
  //MaxLen=10000000;
  //MaxNo=500000000;

  //MaxLen=100;
  //MaxNo=100;
  //MaxNo=16;
  //MaxNo=10000000;
  Max=100000;

Type
  DataFile = File Of Integer;
  TArr=Array[1..200000] OF Integer;

var
  exampleForm1: TexampleForm1;
  ft,ftsort,ft1,ft2,ft3:TEXT;
  fv,fvtemp,fvsort,fv1,fv2,fv3:DataFile;
  a:TArr;
  hh,mm,ss,mss:Word;
  StartTime,EndTime,StartTime1,EndTime1,RunTime:TDateTime;
  MaxNo,MaxLen:Integer;

implementation

{$R *.dfm}

procedure TexampleForm1.FormCreate(Sender: TObject);
begin
  Randomize;
  Memo1.Clear;
  Memo3.Clear;

  AssignFile(ft,'File.txt');
  AssignFile(ftsort,'FileSort.txt');
  AssignFile(ft1,'File1.txt');
  AssignFile(ft2,'File2.txt');
  AssignFile(ft3,'File3.txt');

  AssignFile(fv,'File.dat');
  AssignFile(fvsort,'FileSort.dat');
  AssignFile(fv1,'File1.dat');
  AssignFile(fv2,'File2.dat');
  AssignFile(fv3,'File3.dat');
end;

// 随机产生文本文件
PROCEDURE CreateTextFile(VAR f:TEXT);
VAR i:Integer;
BEGIN
  Rewrite(f);
  FOR i:=1 TO MaxNo DO
    Writeln(f,Random(Max)+1);
  CloseFile(f);
END;

// 随机产生类型文件
PROCEDURE CreateFile(VAR f:DataFile);
VAR i,x:Integer;
BEGIN
  Rewrite(f);
  FOR i:=1 TO MaxNo DO
    BEGIN x:=Random(Max)+1; Write(f,x) END;
  CloseFile(f);
END;

// 显示类型文件
PROCEDURE ShowFile(VAR f:DataFile; Memo:TMemo);
VAR x,i:Integer; line:string;
BEGIN
  Reset(f);
  WHILE NOT eof(f) DO
    BEGIN Read(f,x); line:=IntToStr(x); Memo.Lines.Append(line) END;
  CloseFile(f);
END;

// 选择法排序
PROCEDURE SortBySelectMethod(VAR a:TArr;n:integer);
VAR
  p,i,j,t:integer;
BEGIN
  FOR j:=1 TO n-1 DO
    BEGIN
      p:=j;
      FOR i:=j+1 TO n DO
        IF a[i]<a[p] THEN p:=i;     // 将j到m中的最小数的位置记在p变量中
      t:=a[p]; a[p]:=a[j]; a[j]:=t  // 将j到m中的最小数调到第j位置，这样处理可以减少交换次数
    END;
END;

// 冒泡法排序
PROCEDURE SortByBubbleMethod(VAR a:TArr;n:integer);
VAR
  i,j,t:integer;
  flag:boolean;
BEGIN
  FOR j:=1 TO n DO
    BEGIN
      FOR i:=1 TO n-j DO
        IF a[i]>a[i+1] THEN
          BEGIN
            t:=a[i]; a[i]:=a[i+1]; a[i+1]:=t; flag:=true;
          END;
      if not flag then break;
    END;
END;

// 快速排序
//     为了提高效率，数组a采用全局变量
PROCEDURE qsort(lx,rx:integer);
VAR
  i,j,t:integer;
BEGIN
  i:=lx; j:=rx; t:=a[i];
  REPEAT
    WHILE (a[j]>=t) AND (j>i) DO j:=j-1;
    IF i<j THEN
    BEGIN
      a[i]:=a[j]; i:=i+1;
      WHILE (a[i]<=t) AND (i<j) DO i:=i+1;
      IF i<j THEN
      BEGIN a[j]:=a[i]; j:=j-1; END;
    END;
  UNTIL i=j;
  a[i]:=t; i:=i+1; j:=j-1;
  IF lx<j THEN qsort(lx,j);  // 如果lx=j，则只有一个数据，不必排序
  IF i<rx THEN qsort(i,rx);  // 如果i=rx，则只有一个数据，不必排序
END;

// 合并两个有序文件
PROCEDURE MergeSort(VAR f1,f2,f3:TEXT);
VAR
  finish1,finish2:BOOLEAN;
  x1,x2,choice:INTEGER;
BEGIN
  Reset(f1); Reset(f2); Rewrite(f3);
  IF eof(f1) THEN finish1:=TRUE ELSE BEGIN finish1:=FALSE; Read(f1,x1) END;
  IF eof(f2) THEN finish2:=TRUE ELSE BEGIN finish2:=FALSE; Read(f2,x2) END;
  WHILE NOT (finish1 AND finish2) DO
  BEGIN
    IF (NOT finish1) AND (NOT finish2) THEN
      IF x1<x2 THEN choice:=1 ELSE choice:=2;
    IF finish1       AND (NOT finish2) THEN choice:=2;
    IF (NOT finish1) AND finish2       THEN choice:=1;

    CASE choice OF
      1: BEGIN
           Writeln(f3,x1);
           IF eof(f1) THEN finish1:=TRUE ELSE Read(f1,x1);
         END;
      2: BEGIN
           Writeln(f3,x2);
           IF eof(f2) THEN finish2:=TRUE ELSE Read(f2,x2);
         END;
    END;
  END;
  CloseFile(f1); CloseFile(f2); CloseFile(f3);
END;

// 将有序文件与有序数组合并产生新的有序文件
PROCEDURE MergeFileAndArray(VAR f,fresult:DataFile; a:TArr; alen:Integer);
VAR
  finish1,finish2:BOOLEAN;
  x1,x2,choice,i:INTEGER;
BEGIN
  Reset(f); Rewrite(fresult); i:=1;
  IF eof(f) THEN finish1:=TRUE ELSE BEGIN finish1:=FALSE; Read(f,x1) END;
  IF i>alen THEN finish2:=TRUE ELSE BEGIN finish2:=FALSE; x2:=a[i]; i:=i+1 END;
  WHILE NOT (finish1 AND finish2) DO
  BEGIN
    IF (NOT finish1) AND (NOT finish2) THEN
      IF x1<x2 THEN choice:=1 ELSE choice:=2;
    IF finish1       AND (NOT finish2) THEN choice:=2;
    IF (NOT finish1) AND finish2       THEN choice:=1;

    CASE choice OF
      1: BEGIN
           Write(fresult,x1);
           IF eof(f) THEN finish1:=TRUE ELSE Read(f,x1);
         END;
      2: BEGIN
           Write(fresult,x2);
           IF i>alen THEN finish2:=TRUE ELSE BEGIN x2:=a[i]; i:=i+1 END;
         END;
    END;
  END;
  CloseFile(f); CloseFile(fresult);
END;

procedure TexampleForm1.Button1Click(Sender: TObject);
VAR
  i,j,alen,x,k:Integer;
BEGIN
  MaxNo:=StrToInt(Edit1.Text);
  MaxLen:=StrToInt(Edit2.Text);
  IF MaxLen>ArrMaxLen THEN
    BEGIN ShowMessage('排序数组的长度超过上限!'); Exit END;
  // 先创建二个空文件，用于临时保存中间产生的排序结果
  Rewrite(fv1); CloseFile(fv1);
  Rewrite(fv2); CloseFile(fv2);

  StartTime:=Time;
  CreateFile(fv);
  EndTime:=Time; RunTime:=EndTime-StartTime;
  //ShowFile(fv,Form1.Memo1); Memo1.Lines.Append('------');
  decodeTime(RunTime,hh,mm,ss,mss);
  Memo3.Lines.Append('随机产生长度为'+IntToStr(MaxNo)+'的整数类型文件所用的时间为：'+TimeToStr(RunTime)+' '+IntToStr(mss));

  Memo3.Lines.Append('被排序数据个数：'+IntToStr(MaxNo));
  Memo3.Lines.Append('用于排序的数组长度：'+IntToStr(MaxLen));
  StartTime:=Time;
  Reset(fv); j:=0; k:=0;
  // 分批将数据读入到数组，然后对数组进行排序，再将数组与文件合并，
  // 产生新的有序文件

  WHILE NOT eof(fv) DO
    BEGIN
      StartTime1:=Time;
      i:=0; j:=j+1;
      WHILE (i<MaxLen) AND NOT eof(fv) DO
        BEGIN  i:=i+1; Read(fv,a[i]) END;
      alen:=i;
      IF j=1 THEN
        BEGIN
          EndTime1:=Time; RunTime:=EndTime1-StartTime1;
          decodeTime(RunTime,hh,mm,ss,mss);
          Memo3.Lines.Append('读取第'+IntToStr(j)+'批数据所用的时间为：'+TimeToStr(RunTime)+' '+IntToStr(mss));
        END;

      StartTime1:=Time;
      //SortBySelectMethod(a,alen);   // 采用选择法对数组进行排序
      qsort(1,alen);                  // 采用快速排序对数组进行排序
      IF j=1 THEN
        BEGIN
          EndTime1:=Time; RunTime:=EndTime1-StartTime1;
          decodeTime(RunTime,hh,mm,ss,mss);
          Memo3.Lines.Append('对第'+IntToStr(j)+'个数组进行排序所用的时间为：'+TimeToStr(RunTime)+' '+IntToStr(mss));
        END;

      StartTime1:=Time;
      IF k=0 THEN MergeFileAndArray(fv1,fv2, a, alen)
      ELSE MergeFileAndArray(fv2,fv1, a, alen);
      EndTime1:=Time; RunTime:=EndTime1-StartTime1;
      decodeTime(RunTime,hh,mm,ss,mss);
      Memo3.Lines.Append('对第'+IntToStr(j)+'个数组进行合并所用的时间为：'+TimeToStr(RunTime)+' '+IntToStr(mss));

      k:=k+1; IF k=2 THEN k:=0;
    END;
    CloseFile(fv);
  EndTime:=Time; RunTime:=EndTime-StartTime;
  decodeTime(RunTime,hh,mm,ss,mss);
  Memo3.Lines.Append('对所有数据进行排序所用的时间为：'+TimeToStr(RunTime)+' '+IntToStr(mss));
  Memo3.Lines.Append('');

  //ShowMessage('排序结束！');
  IF CheckBox1.Checked THEN
    BEGIN
      IF MaxNo<=1000 THEN
        BEGIN
          Memo1.Clear;
          IF k=0 THEN ShowFile(fv1,exampleForm1.Memo1) ELSE ShowFile(fv2,exampleForm1.Memo1);
        END
      ELSE ShowMessage('数据太多，不宜显示！');
    END;

  // 将排序结果保存到FileSort.dat文件
  IF k=0 THEN AssignFile(fvtemp,'File1.dat') ELSE AssignFile(fvtemp,'File2.dat');
  Rewrite(fvsort); Reset(fvtemp);
  WHILE NOT eof(fvtemp) DO
    BEGIN Read(fvtemp,x); Write(fvsort,x); END;
  CloseFile(fvsort); CloseFile(fvtemp);

END;

procedure TexampleForm1.Button2Click(Sender: TObject);
VAR i,x:Integer;
begin
  Reset(fvsort); i:=0; Memo1.Clear;
  WHILE NOT eof(fvsort) AND (i<1000) DO
    BEGIN
      Read(fvsort,x); Memo1.Lines.Append(IntToStr(x)); i:=i+1;
    END;
  IF NOT eof(fvsort) THEN Memo1.Lines.Append('......');
  CloseFile(fvsort);
end;

end.