文档章节

极快的正整数排序函数

涂孟超
 涂孟超
发布于 2014/09/26 15:38
字数 281
阅读 15
收藏 0

实现原理: 对比二进制位.
unit Unit1;

interface

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

type
  TForm1 = class(TForm)
    Button1: TButton;
    Memo1: TMemo;
    procedure Button1Click(Sender: TObject);
    procedure FormCreate(Sender: TObject);
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

type
  TIntArr = array of Integer;

{极快的正整数排序函数}
procedure IntSort(arr:TIntArr; low:Integer=0; high:Integer=-1; k:Cardinal=$80000000; c:Cardinal=1);
var
  i,j,x: Integer;
begin
  if high = -1 then high := Length(arr) -1;
  i := low;
  j := high;
  while (i < j) do
  begin
    while (arr[j] and k <> 0) and (i < j) do Dec(j);
    while (arr[i] and k = 0) and (i < j) do Inc(i);
    if i < j then
    begin
      x := arr[j];
      arr[j] := arr[i];
      arr[i] := x;
    end else begin
      if arr[j] and k <> 0 then Dec(i) else Inc(j);
      Break;
    end;
  end;
  if k > c then
  begin
    if low < i then IntSort(arr, low, i, k div 2);
    if j < high then IntSort(arr, j, high, k div 2);
  end;
end;

{测试}
procedure TForm1.Button1Click(Sender: TObject);
var
  MyArr: TIntArr;
  i: Integer;
  t: Int64;
begin
  SetLength(MyArr, MAXWORD);
  for i := Low(MyArr) to High(MyArr) do MyArr[i] := Random(MaxInt);
  
  t := GetTickCount;
  
  IntSort(MyArr); //调用排序函数
  
  Text := IntToStr(GetTickCount - t);

  Memo1.Clear;
  for i := 0 to Length(MyArr)-1 do
  begin
    if i mod 1000 = 0 then
      Memo1.Lines.Add(IntToStr(MyArr[i]));
  end;
end;

procedure TForm1.FormCreate(Sender: TObject);
begin
  Memo1.Clear;
  Memo1.Align := alLeft;
  Memo1.ScrollBars := ssVertical;
end;

end.

 
 
 
 
 

 

 

  

本文转载自:http://www.cnblogs.com/del/archive/2009/05/01/1447325.html

共有 人打赏支持
涂孟超
粉丝 12
博文 2011
码字总数 14107
作品 0
深圳
程序员
编程珠玑--位图法排序

位图法是《编程珠玑》第一章中出现的磁盘排序算法。 题目:一个最多包含n个正整数的文件,每个数都小于n,其中n=10^7,且所有正整数都不重复。求如何将这n个正整数升序排列。 约束:最多有1MB...

王二狗子11
01/08
0
0
三种方法实现Hadoop(MapReduce)全局排序(1)

我们可能会有些需求要求MapReduce的输出全局有序,这里说的有序是指Key全局有序。但是我们知道,MapReduce默认只是保证同一个分区内的Key是有序的,但是不保证全局有序。基于此,本文提供三种...

CoXie的大数据世界
08/12
0
0
Comparator和Comparable在排序中的应用

当需要排序的集合或数组不是单纯的数字型时,通常可以使用Comparator或Comparable,以简单的方式实现对象排序或自定义排序。 一、Comparator 强行对某个对象collection进行整体排序的比较函数...

stefanliao
2012/05/29
0
0
Comparable接口

public interface Comparable<T> 此接口强行对实现它的每个类的对象进行整体排序。这种排序被称为类的自然排序,类的 compareTo 方法被称为它的自然比较方法。 实现此接口的对象列表(和数组...

Zenith-Lee
2014/02/19
37
0
Wannafly模拟赛4:A -Laptop(后缀)

题目链接 Laptop Time limit:1000ms Memory limit:262144K Problem Description FST是一名可怜的小朋友,他很强,但是经常fst,所以rating一直低迷。 但是重点在于,他非常适合ACM!并在最近...

xp731574722
2017/10/26
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

新工作与老项目

新的工作不知不觉的干了一个多月了。怎么说呢,跟想象中的差别不少,本来想的能进来跟大公司的同事能有很多交流,能在团队中跟大牛学习更快。结果公司的这个项目上只有两个程序员,项目是十年...

zypy333
7分钟前
0
0
mysql 在windows的安装

mysql 在windows的安装。 mysql64位的server的下载地址是: https://dev.mysql.com/downloads/mysql/ 使用的是5.7版本。 下载安装包,解压至D:\mysql\mysql-5.7.23-winx64\ 在D:\mysql\mysq...

lxzh504
20分钟前
1
0
云技术、大数据(hadoop)入门常见问题回答

当我们学习一门新技术的时候,我们总是产生各种各样的问题,这些问题整理出来,包括该 1.如何学习hadoop? 2.hadoop常见问题? 3.还有hbase、hive安装使用等? 你知道搭建hadoop平台需要些什...

董黎明
20分钟前
1
0
小程序自定义底部tab

场景 1.tabBar是在内页而非首页,这时就不得不自定义一个tabBar了 2.自定义风格 3.子页数量超过5个,得到更多了tab 4.改变点击tab默认事件,比如出登录界面,或者弹出上拉子菜单等 步骤 1.照...

萤火的萤火
25分钟前
1
0
shell炫技

1.为脚本添加“--help” #!/bin/shif [ ${#@} -ne 0 ] && [ "${@#"--help"}" = "" ]; then printf -- '...help...\n'; exit 0;fi; 2.输出字体添加颜色 https://misc.flogisoft.com......

HJCui
26分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部