文档章节

《Delphi 算法与数据结构》学习与感悟[1]: 通过 "顺序查找" 与 "二分查找" 说明算法的重要性

涂孟超
 涂孟超
发布于 2014/09/26 15:37
字数 394
阅读 14
收藏 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);
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

{顺序查找函数}
function SeqSearch(List: TStringList; const str: string): Integer;
var
  i: Integer;
begin
  for i := 0 to List.Count - 1 do
    if CompareText(List[i], str) = 0 then begin Result := i; Exit; end;
  Result := -1;
end;

{二分查找函数; 二分查找只能针对有序列表}
function BinarySearch(List: TStringList; const str: string): Integer;
var
  L,R,M: Integer;
  CompareResult: Integer;
begin
  Result := -1;
  L := 0;
  R := List.Count - 1;

  while L <= R do
  begin
    M := (L + R) div 2;
    CompareResult := CompareText(List[M], str);
    if CompareResult < 0 then L := M + 1 else
    if CompareResult > 0 then R := M - 1 else
    begin
      Result := M;
      Exit;
    end;
  end;
end;

{对比测试}
procedure TForm1.Button1Click(Sender: TObject);
var
  TestList: TStringList;
  i: Integer;
  n1,n2: Int64;
  Count1,Count2: Integer;
  s: string;
const
  num = 1000000; {准备测试百万个数据}
begin
  TestList := TStringList.Create;
  for i := 0 to num-1 do TestList.Add(IntToHex(i,8)); {准备有序的测试值列表}

  Memo1.Clear;
  Count1 := 0;
  Count2 := 0;

  {搞 10 实验}
  for i := 0 to 9 do
  begin
    {产生范围内的随机字串}
    Randomize;
    s := IntToHex(Random(num),8);

    {顺序查找}
    QueryPerformanceCounter(n1);
    SeqSearch(TestList, s);
    QueryPerformanceCounter(n2);
    Memo1.Lines.Add(IntToStr(n2-n1)+ #9);
    Count1 := Count1 + (n2-n1);

    {二分查找}
    QueryPerformanceCounter(n1);
    BinarySearch(TestList, s);
    QueryPerformanceCounter(n2);
    Memo1.Lines[i] := Memo1.Lines[i] + IntToStr(n2-n1);
    Count2 := Count2 + (n2-n1);
  end;

  Memo1.Lines.Add('----------------');
  Memo1.Lines.Add('平均值:');
  Memo1.Lines.Add(IntToStr(Count1 div 10)+ #9 + IntToStr(Count2 div 10));
  Memo1.Lines.Add('----------------');
  Memo1.Lines.Insert(0, '顺序'#9'二分');

  TestList.Free;
end;

end.

 
 
 
 
 

 

 

  
二分查找太快了, 用 GetTickCount 测试不出来, 只好使用 QueryPerformanceCounter;
另外 TStringList.Find 方法也是使用了 "二分查找" 的办法.

本文转载自:http://www.cnblogs.com/del/archive/2008/03/17/1109391.html

共有 人打赏支持
涂孟超
粉丝 12
博文 2011
码字总数 14107
作品 0
深圳
程序员
私信 提问
Java实现的二分查幸运飞艇平台出租找算法[递归]

二分查找又幸运飞艇平台出租 haozbbs.comQ1446595067 称折半查找,它是一种效率较高的查找方法。 折半查找的算法思想是将数列按有序化(递增或递减)排列,查找过程中采用跳跃式方式查找,即先...

oskksk
2018/07/10
0
0
数据结构和算法(What Why How)

数据结构和算法是什么? 从广义上讲,数据结构就是指一组数据的存储结构。算法就是操作数据的一组方法。 从狭义上讲,是指某些著名的数据结构和算法,比如队列、堆、栈、二分查找、动态规划等...

hardyyao
2018/10/05
0
0
送书 | 你一定能看懂的算法基础书(代码示例基于Python)

本文引自图灵教育《算法图解》 你一定能看懂的算法基础书;代码示例基于Python;400多个示意图,生动介绍算法执行过程;展示不同算法在性能方面的优缺点;教会你用常见算法解决每天面临的实际...

dqcfkyqdxym3f8rb0
2017/11/24
0
0
2018年6月前端面试经历(中)

前言 上一篇文章,写了一些出去面试会考到的笔试题,不是很全(哈哈哈,基本上都是靠脑子记的,有些都忘记了~) 传送门在这里:2018年6月前端面试经历(上)~~~ 这篇我会写出一些我碰到的算法...

我母鸡啊!
2018/07/05
0
0
分块查找(Blocking Search)

1、定义 分块查找(Blocking Search)又称索引顺序查找。它是一种性能介于顺序查找和二分查找之间的查找方法。 2、基本思想 分块查找的基本思想是: (1)首先查找索引表 索引表是有序表,可采...

野渡书生
2016/04/28
47
1

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周三乱弹 —— 孤独到都和病毒发生了感情了

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @-冰冰棒- :#今日歌曲推荐# 逃跑计划《一万次悲伤 (Live)》 《一万次悲伤 (Live)》- 逃跑计划 手机党少年们想听歌,请使劲儿戳(这里) 现在...

小小编辑
36分钟前
11
4
test

//// main.c// Test//// Created by 吕颖 on 2019/1/16.// Copyright © 2019年 carmen. All rights reserved.//#include <stdio.h>#include <stdlib.h>#include <t......

carmen-ly
今天
1
0
Android webview热门组件agentweb:4.0.2无法自适应的问题

Android webview热门组件agentweb:4.0.2无法自适应的问题 //设置自适应屏幕,两者合用mAgentWeb.getAgentWebSettings().getWebSettings().setUseWideViewPort(true); //将图片调整到适合w...

Gemini-Lin
今天
5
0
如何维护一个自己的 golang doc 服务

本文内容是如何维护一个golang 在线的doc 服务。 1 什么是godoc ? godoc 是 golang 官方提供的文档生成工具, 2 为什么要有godoc ? 我们经常遇到一个问题,就是代码和文档不一致,线上代码版...

鼎铭
今天
5
0
js中的对象创建的模式以及继承模式

对象创建模式: 工厂模式 构造函数模式 原型模式 继承模式 原型式继承 寄生式继承 构造函数 原型式和构造函数的组合式(缺点:运行两次超类类函数,积累函数的属性被挂载在原型对象上和实例对...

莫西摩西
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部