- 浏览: 1205611 次
- 性别:
- 来自: 深圳
文章分类
- 全部博客 (718)
- HTML (13)
- JS基础 (23)
- JS应用 (40)
- AJAX (6)
- JSP相关 (12)
- JAVA基础 (52)
- JAVA应用 (74)
- APPLET (11)
- SWING\RCP (2)
- JAVA反射 (6)
- 设计模式 (26)
- 数据库设计 (20)
- Struts (35)
- Struts2 (12)
- Spring (22)
- Hibernate (45)
- Ibatis (18)
- mybatis (3)
- SSH (8)
- UML (5)
- WebService (3)
- XML (16)
- Log4j (7)
- WEB容器 (26)
- 数据结构 (36)
- Linux (34)
- Ruby on Rails (1)
- 其它技术 (27)
- IDE配置 (15)
- 项目实战 (2)
- Oracle (69)
- JAVA报表 (7)
- Android学习 (2)
- 博客链接 (1)
- 网络基础 (1)
- WEB集群 (1)
- .Net开发 (11)
- PB (4)
- 系统构建 (15)
最新评论
-
jnjeC:
牛逼啊哥们,讲得太好了
Maven仓库理解、如何引入本地包、Maven多种方式打可执行jar包 -
九尾狐的yi巴:
很好 感谢!
Itext中文处理(更新版) -
luweifeng1983:
有用的,重启一下嘛。
设置eclipse外部修改文件后自动刷新 -
Master-Gao:
设置了也不管用,怎么破呢?
设置eclipse外部修改文件后自动刷新 -
aigo_h:
锋子还有时间写博客,还是很闲哈!
Add directory entries问题
http://www.cnblogs.com/ziyiFly/archive/2008/09/10/1288508.html
分配排序的基本思想:排序过程无须比较关键字,而是通过"分配"和"收集"过程来实现排序.它们的时间复杂度可达到线性阶:O(n)。
1、箱排序的基本思想
箱排序也称桶排序(Bucket Sort),其基本思想是:设置若干个箱子,依次扫描待排序的记录R[0],R[1],…,R[n-1],把关键字等于k的记录全都装入到第k个箱子里(分配),然后按序号依次将各非空的箱子首尾连接起来(收集)。
【例】要将一副混洗的52张扑克牌按点数A<2<…<J<Q<K排序,需设置13个"箱子",排序时依次将每张牌按点数放入相应的箱子里,然后依次将这些箱子首尾相接,就得到了按点数递增序排列的一副牌。
2、箱排序中,箱子的个数取决于关键字的取值范围。
若R[0..n-1]中关键字的取值范围是0到m-1的整数,则必须设置m个箱子。因此箱排序要求关键字的类型是有限类型,否则可能要无限个箱子。
3、箱子的类型应设计成链表为宜
一般情况下每个箱子中存放多少个关键字相同的记录是无法预料的,故箱子的类型应设计成链表为宜。
4、为保证排序是稳定的,分配过程中装箱及收集过程中的连接必须按先进先出原则进行。
(1) 实现方法一
每个箱子设为一个链队列。当一记录装入某箱子时,应做人队操作将其插入该箱子尾部;而收集过程则是对箱子做出队操作,依次将出队的记录放到输出序列中。
(2) 实现方法二
若输入的待排序记录是以链表形式给出时,出队操作可简化为是将整个箱子链表链接到输出链表的尾部。这只需要修改输出链表的尾结点中的指针域,令其指向箱子链表的头,然后修改输出链表的尾指针,令其指向箱子链表的尾即可。
5、算法简析
分配过程的时间是O(n);收集过程的时间为O(m) (采用链表来存储输入的待排序记录)或O(m+n)。因此,箱排序的时间为O(m+n)。若箱子个数m的数量级为O(n),则箱排序的时间是线性的,即O(n)。
注意:
箱排序实用价值不大,仅适用于作为基数排序(下节介绍)的一个中间步骤。
桶排序
箱排序的变种。为了区别于上述的箱排序,姑且称它为桶排序(实际上箱排序和桶排序是同义词)。
1、桶排序基本思想
桶排序的思想是把[0,1)划分为n个大小相同的子区间,每一子区间是一个桶。然后将n个记录分配到各个桶中。因为关键字序列是均匀分布在[0,1)上
的,所以一般不会有很多个记录落入同一个桶中。由于同一桶中的记录其关键字不尽相同,所以必须采用关键字比较的排序方法(通常用插入排序)对各个桶进行排
序,然后依次将各非空桶中的记录连接(收集)起来即可。
注意:
这种排序思想基于以下假设:假设输入的n个关键字序列是随机分布在区间[0,1)之上。若关键字序列的取值范围不是该区间,只要其取值均非负,我们总能将所有关键字除以某一合适的数,将关键字映射到该区间上。但要保证映射后的关键字是均匀分布在[0,1)上的。
2、桶排序算法
伪代码算法为:
void BucketSon(R)
{ //对R[0..n-1]做桶排序,其中0≤R[i].key<1(0≤i<n)
for(i=0,i<n;i++) //分配过程.
将R[i]插入到桶B[「n(R[i].key)」]中; //可插入表头上
for(i=0;i<n;i++) //排序过程
当B[i]非空时用插人排序将B[i]中的记录排序;
for(i=0,i<n;i++) //收集过程
若B[i]非空,则将B[i]中的记录依次输出到R中;
}
注意:
实现时需设置一个指针向量B[0..n-1]来表示n个桶。但因为任一记录R[i]的关键字满足:0≤R[i].key<1(0≤i≤n-1),
所以必须将R[i].key映射到B的下标区间[0,n-1)上才能使R[i]装入某个桶中,这可通过└n*(R[i].key)┘来实现。
3、桶排序示例
R[0..9]中的关键字为 (0.78,0.17,0.39,0.26,0.72,0.94,0.21, 0.12,0.23,0.68),用算法BucketSort排序的过程【参见动画演示】。
分析:
这里n=10,故B[0..9]这10个桶表示的子区间分别是[0,0.1),[0.1,0.2),…,[0.9,1)。
收集过程只要按B[0],B[1],…,B[9]的次序将各非空桶首尾链接起来,或将其输出到R[0..9)中即可。
4、桶排序算法分析
桶排序的平均时间复杂度是线性的,即O(n)。但最坏情况仍有可能是O(n2)。
箱排序只适用于关键字取值范围较小的情况,否则所需箱子的数目m太多导致浪费存储空间和计算时间。
【例】n=10,被排序的记录关键字ki取值范围是0到99之间的整数(36,5,16,98,95,47, 32,36,48)时,要用100个箱子来做一趟箱排序。(即若m=n2时,箱排序的时间O(m+n)=O(n2))。
发表评论
-
排序算法与查找算法
2014-09-01 10:17 357八大排序算法: http://blog.csdn.net ... -
用递归与非递归实现斐波拉希数列
2013-05-15 00:46 1866如下: package com.test; publ ... -
利用LinkedList制作一个栈
2012-12-19 21:55 841import java.util.LinkedList; ... -
递归问题求解学习一
2009-04-22 14:12 696http://blog.csdn.net/lixiaoshan ... -
算术逻辑推理学习
2009-04-23 15:52 961数字推理考察的是对 ... -
由递归所想到的:如何将字符串或者数字转换成大写货币的问题
2009-04-24 11:54 1181这个问题同事在面试的时候遇到过,最近在看有关递归的问题时 h ... -
数据结构基础--排序: 各种排序算法全分析
2009-05-06 11:35 1421http://www.cnblogs.com/ziyiFly/ ... -
数据结构-算法: 分配排序(基数分配排序法)
2009-05-06 11:41 1044http://www.cnblogs.com/ziyiFly/ ... -
数据结构-排序: 两路归并排序算法
2009-05-06 11:44 1690数据结构-排序: 两路归 ... -
数据结构-排序: 插入排序(直接插入排序法)
2009-05-06 11:45 1180数据结构-排序: 插入排 ... -
数据结构-算法: 插入排序(希尔排序法)
2009-05-06 11:45 1425数据结构-算法: 插入排 ... -
数据结构-排序: 交换排序(快速排序法)
2009-05-06 11:46 1453数据结构-排序: 交换排序(快速排序法) 1、算法思想 ... -
数据结构-排序: 选择排序(堆选择排序法)
2009-05-06 11:47 873数据结构-排序: 选择排 ... -
数据结构-排序: 交换排序(冒泡排序法)
2009-05-06 11:47 1007数据结构-排序: 交换排序(冒泡排序法) 冒泡排序(Bu ... -
数据结构-排序: 选择排序(直接选择排序法)
2009-05-06 11:48 943数据结构-排序: 选择排序(直接选择排序法) 直接选择排 ... -
C#实现--单链表(链式)
2009-05-06 11:49 1359C#实现--单链表(链式) using Syste ... -
C#实现二叉树(三元素式)及二叉树遍历的四种方法
2009-05-06 11:50 1430C#实现二叉树(三元素式) ... -
JAVA排序类汇总
2009-05-06 11:54 1166package com.softeem.jbs.lesson4 ... -
谈谈防 SQL 注入式攻击策略
2009-05-07 09:30 1391谈谈防 SQL 注入式攻击 ... -
二进制数转换为八进制, 十六进制数的算法
2009-05-07 09:44 1277using System; using System.Col ...
相关推荐
最快的排序算法 谁才是最强的排序算法:快速排序-归并排序-堆排序,排序算法数据结构
内容涵盖了数据结构和算法的基本原理,涉及数组、广义表、链表、散列表、树、图、排序搜索算法以及更多概率算法和动态规则等高级算法。此外,书中还提供了.NET框架类库中的C#语言实现的数据结构和算法。 《数据结构...
此文件为数据结构中的九种排序算法,包含一些排序方法的过程,其九种排序包括:直接插入排序,折半插入排序,希尔排序,冒泡排序,快速排序,选择排序,堆排序,归并排序,基数排序!
数据结构与算法:ch10_排序.ppt
算法:C语言实现第1-4部分基础知识、数据结构、排序及搜索
数据结构 课程设计 多种排序算法 有界面 数据结构 课程设计 多种排序算法 有界面 数据结构 课程设计 多种排序算法 有界面 数据结构 课程设计 多种排序算法 有界面 数据结构 课程设计 多种排序算法 有界面
比二分法更快的算法-算法问题:扔杯子的几种方法,排序算法数据结构 最快的排序算法
算法与数据结构它们分别涵盖了以下主要内容: 数据结构(Data Structures): 逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树)、图结构(有向图、无向图等)...
数据结构-排序算法的实现(代码+报告)
1、创建排序类。 2、提供操作:选择排序、冒泡排序、插入排序、基数排序、快速排序、归并排序。(快速排序、归并排序讲到之后再做) 3、*能够显示各种排序算法的中间过程。
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
包括基本算法分析原理,基本数据结构、抽象数据结构、递归和树等数据结构知识,选择排序、插入排序、冒泡排序、希尔排序、快速排序方法、归并和归并排序方法、优先队列与堆排序方法、基数排序方法以及特殊用途的排序...
最快的排序算法 计算机最快的算法-史上14个最快速算法:孩子的计算能力爆表!大脑堪比计算机!...,排序算法数据结构
排序是一个难点,里面包含了堆排序等等有关排序的算法,希望对大家有所帮助...this is a good resource and way to study sort the number that what you wanted,please come and download it.
算法与数据结构涵盖了以下主要内容: 数据结构(Data Structures): 逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树)、图结构(有向图、无向图等)以及集合和...
算法:C语言实现 (第1-4部分)基础知识、数据结构、排序及搜索(原书第3版) 本书是Sedgewick彻底修订和重写的C算法系列的第一本。全书分为四部分,共16章。第一部分“基础知识”(第1—2章)介绍基本算法分析原理。...
数据结构课程设计,C语言,七大排序算法比较