各种排序查询的算法效率比较

« 如何获取厦门SMX搜索引擎营销大会 301跳转在那些情况下用到 »

2008-03-18搜索引擎

3,650 views

一排序

排序方式

时间复杂度

空间复杂度

稳定性

算法描述

备注:

时间复杂度O(1)<O(n)<O(logn)<O(nlogn)<O(n2)

1,2,3属于插入排序; 4,5属于交换排序; 6,7属于选择排序.

记录数大时,选择改进算法; 记录数较小时,可采用简单排序(如1,4,6)

平均情况下,快速排序速度是最快的,推荐使用.

稳定性指具有相同值的记录在排序时相对次序不改变.

内排序: 数据量较少时,仅在内存中进行;

外排序: 数据量较大时,在内外存中进行数据交换(常用归并排序,文件来解决)

二查询

检索表: 检索所依赖的数据结构.

查询定义: 根据KEY,在检索表中确定VALUE的值.

1 线性表

1)顺序检索: 采用逆向检索

2)折半检索

3)分块检索

2 树表

1)二叉排序树

2)平衡的二叉排序树

3)B树

4)红黑树

3 HASH表

最快只需常数时间.

4 其它数据结构

1)序列容器

VectOr: 类似线性表

List 类似线性表

2)关联容器

Map: 图的检索, 一对一

Multimap: 一对多

Hashmap: 常数时间检索,用hash_table实现.

检索算法评估: (平均检索长度ASL)

下面是检索算法效率列表:

检索表	检索算法	ASL	算法描述
线性表	顺序	(n+1)/2
	折半	Log2(n+1)-1 (n>>100)	适用于有序表
	分块
树表	二叉排序树
	平衡二叉排序树
	B树
	红黑树
HASH表

日志信息 »

该日志于2008-03-18 03:46由阿猎发表在搜索引擎分类下，你可以发表评论。除了可以将这个日志以保留源地址及作者的情况下引用到你的网站或博客，还可以通过RSS 2.0订阅这个日志的所有评论。

26条评论▼

网络营销课程说：

2011-03-28 于

好复杂呀！看不大懂，回去慢慢研究下到
单人操作说：

2011-11-06 于

这个确实很复杂呢，搞不懂，是数据算法吗？
Basil Laraia 说：

2012-01-14 于

I just want to say I am very new to blogging and site-building and seriously loved you’re web-site. More than likely I’m going to bookmark your blog . You really come with amazing articles and reviews. Kudos for sharing with us your blog site.
Article Writing Service 说：

2012-01-19 于

A unique discussion may be worth comment. I do believe that you should create more on this kind of topic, may well be a taboo subject but commonly people are there are not enough to speak for such issues. To the next. Best wishes
dumpster rental highland ks 说：

2012-01-24 于

Wonderful information, thank you for posting.
J. Joshua Beistle 说：

2012-01-25 于

Good read. I saved the page for future visit.
Jersey Jobs 说：

2012-01-25 于

Whenever a man has cast a longing eye on offices, a rottenness begins in his conduct. ~Thomas Jefferson
appareil photo bridge canon 说：

2012-01-27 于

I see something truly interesting about your website so I saved to bookmarks .
vps hosting 说：

2012-01-28 于

you’re in reality a excellent webmaster. The web site loading pace is incredible. It sort of feels that you are doing any unique trick. Furthermore, The contents are masterpiece. you have done a magnificent activity in this topic!
vps hosting 说：

2012-01-28 于

Wow! Thank you! I permanently wanted to write on my blog something like that. Can I take a portion of your post to my site?
robot multifonction pas cher 说：

2012-01-29 于

As I website possessor I think the written content here is very good , thanks for your efforts.
online movies 说：

2012-01-29 于

I’m still learning from you, but I’m improving myself. I absolutely liked reading all that is posted on your blog.Keep the posts coming. I liked it!
decodeur tnt 说：

2012-01-29 于

I like this web site very much, Its a very nice situation to read and find information. “It is not what we take up, but what we give up, that makes us rich.” by Henry Ward Beecher.
Marge Schibi 说：

2012-01-29 于

Fantastic goods from you, man. I’ve understand your stuff previous to and you are just too magnificent. I really like what you have acquired here, really like what you are saying and the way in which you say it. You make it entertaining and you still take care of to keep it wise. I cant wait to read much more from you. This is really a wonderful site.
echelle telescopique 说：

2012-01-29 于

I truly enjoy examining on this website , it holds excellent posts . “The longing to produce great inspirations didn’t produce anything but more longing.” by Sophie Kerr.
tables basses 说：

2012-01-29 于

My spouse and i still can’t quite think I could often be one of those studying the important tips found on your web site. My family and I are sincerely thankful for the generosity and for providing me the advantage to pursue the chosen profession path. Thanks for the important information I managed to get from your web page.
robotmenager 说：

2012-01-30 于

Perfectly composed articles , regards for entropy.
trampoline avec filet 说：

2012-01-30 于

I like the efforts you have put in this, appreciate it for all the great posts.
ruletka 说：

2012-01-31 于

I do agree with all the ideas you’ve presented in your post. They are very convincing and will definitely work. Still, the posts are too short for novices. Could you please extend them a little from next time? Thanks for the post.
montre gps 说：

2012-01-31 于

I believe this is one of the so much significant information for me. And i am satisfied reading your article. But should statement on some normal things, The website taste is great, the articles is in point of fact nice . Good activity, cheers.
Tim 说：

2012-01-31 于

I haven’t checked in here for some time since I thought it was getting boring, but the last several posts are great quality so I guess I’ll add you back to my daily bloglist. You deserve it my friend
Blepharoplasty 说：

2012-01-31 于

Your points are fascinating. Thank you for writing this.
table à langer 说：

2012-01-31 于

hello there and thank you for your information – I have definitely picked up something new from right here. I did however expertise several technical points using this website, since I experienced to reload the website lots of times previous to I could get it to load correctly. I had been wondering if your web host is OK? Not that I am complaining, but sluggish loading instances times will very frequently affect your placement in google and can damage your high quality score if ads and marketing with Adwords. Anyway I am adding this RSS to my email and could look out for a lot more of your respective interesting content. Make sure you update this again soon..
white ceramic watches for women 说：

2012-01-31 于

You completed various fine points there. I did a search on the topic and found the majority of people will go along with with your blog.
trampoline pas cher 说：

2012-01-31 于

You completed several nice points there. I did a search on the issue and found the majority of persons will agree with your blog.
Shelly Montee 说：

2012-02-01 于

Thanks for the sensible critique. Me & my neighbor were just preparing to do a little research on this. We got a grab a book from our area library but I think I learned more clear from this post. I’m very glad to see such great info being shared freely out there.

SEO博客,在SEO中实战中的阿猎SEO项目管理博客