`

数据结构-算法: 分配排序(箱分配排序)

阅读更多

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))。

分享到:
评论

相关推荐

    数据结构学习笔记排序算法:基数排序

    数据结构学习笔记排序算法:基数排序数据结构学习笔记排序算法:基数排序数据结构学习笔记排序算法:基数排序数据结构学习笔记排序算法:基数排序数据结构学习笔记排序算法:基数排序数据结构学习笔记排序算法:基数...

    数据结构-排序算法的实现(代码+报告)

    ### 数据结构-排序算法的实现知识点详解 #### 实验背景及目标 本次实验的主要目的是让学生深入理解并掌握几种常见的排序算法及其应用场景。通过动手实践,不仅能够加深对各种排序算法工作原理的理解,还能够培养...

    Java编程语言中的数据结构与算法:深入理解与实践指南.zip

    在Java编程语言中,数据结构和算法是两个至关重要的概念,它们构成了软件开发的基础。数据结构是组织和存储数据的方式,而算法则是解决问题或执行任务的步骤。本指南将深入探讨这两个主题,帮助开发者提高代码效率,...

    数据结构与算法:C#语言描述(中文)

    ### 数据结构与算法:C#语言描述 #### 引言 数据结构与算法是软件开发领域不可或缺的基础知识,尤其对于专业程序员来说尤为重要。随着C#语言的广泛应用,使用该语言来学习和理解数据结构与算法变得更为现实和高效...

    数据结构与算法分析_Java语言描述(第2版) 源代码

    《数据结构与算法分析_Java语言描述(第2版) 源代码》是一本深入探讨数据结构和算法的书籍,其源代码是学习和理解书中理论的重要实践资源。这本书籍主要面向计算机科学专业的学生以及对算法有深入研究需求的开发者。...

    2018JAVA经典教程:数据结构与算法经典问题解析-Java语言描述

    《2018JAVA经典教程:数据结构与算法经典问题解析》是一本深入探讨Java语言中数据结构和算法实现的教程。这本书旨在帮助读者理解并掌握如何使用Java有效地设计和解决各种计算问题。数据结构是计算机科学的基础,而算...

    数据结构实验-排序算法

    排序算法则是数据结构中的重要部分,它们用于对一组数据进行有序排列。在这个实验中,我们将关注六种不同的排序算法:选择排序、冒泡排序、插入排序、基数排序以及快速排序和归并排序。下面是对这些排序算法的详细...

    数据结构--九种排序算法 --排序001.cpp

    此文件为数据结构中的九种排序算法,包含一些排序方法的过程,其九种排序包括:直接插入排序,折半插入排序,希尔排序,冒泡排序,快速排序,选择排序,堆排序,归并排序,基数排序!

    数据结构与算法

    ### 数据结构与算法 #### 知识点一:数据结构概览 - **定义**:数据结构是指在计算机科学中,一组数据的存储结构。它不仅包括存储结构本身,还包括在此结构上的各种操作。 - **分类**:主要分为两大类: - **线性...

    数据结构与算法:ch10_排序.ppt

    数据结构与算法:ch10_排序.ppt

    算法:算法C语言实现 第1-4部分 基础知识、数据结构、排序及搜索

    算法:C语言实现 (第1-4部分)基础知识、数据结构、排序及搜索(原书第3版) 本书是Sedgewick彻底修订和重写的C算法系列的第一本。全书分为四部分,共16章。第一部分“基础知识”(第1—2章)介绍基本算法分析原理。...

    数据结构与算法分析C语言描述第2版源码

    这本书深入浅出地介绍了各种数据结构(如数组、链表、树、图)以及算法(排序、查找、图算法等)的设计与分析。源码文件包含了书中所有示例程序,供读者实践和学习。 1. 数据结构: - 数组:基本的数据组织形式,...

    算法:C语言实现第1-4部分基础知识、数据结构、排序及搜索

    本资源“算法:C语言实现第1-4部分基础知识、数据结构、排序及搜索”涵盖了C语言编程的基础知识,以及在计算科学中至关重要的数据结构、排序和搜索算法。 首先,基础知识部分主要涉及C语言的语法、变量、控制结构...

    数据结构与算法分析答案

    数据结构与算法分析是计算机科学中的核心课程,它涉及到如何有效地组织和操作数据,以及设计高效算法解决问题。《Data Structures and Algorithm Analysis in C(2nd Edition)》是Mark Allen Weiss撰写的一本经典教材...

    数据结构—实用C语言

    数据结构是计算机科学中的核心概念,它涉及到如何在内存中有效地组织和管理数据,以便进行高效的操作。在C语言中实现数据结构,可以让你深入理解底层机制,这对于软件开发至关重要。"数据结构—实用C语言"这个主题...

    数据结构算法【啊哈、java数据算法与结构等】

    在这个完整的资料包"数据结构算法【啊哈、java数据算法与结构等】"中,我们聚焦于如何使用Java语言来实现各种数据结构和算法。啊哈算法通常指的是那些具有独特洞察力或巧妙解法的算法,它们能提供解决问题的新视角。...

    数据结构与算法-java

    数据结构与算法是计算机科学的基础,对于理解和设计高效的软件至关重要。在Java编程中,理解这些概念可以帮助开发者编写出性能优异的程序。以下是基于标题“数据结构与算法-java”及描述中提到的“数据结构与算法...

    数据结构--排序 很细致

    数据结构中的排序是计算机科学中一个基础且重要的概念,它涉及到如何有效地组织和处理大量数据。排序算法的主要目标是将一组无序的数据元素按照特定的标准(通常是升序或降序)排列成一个有序序列。本篇文章主要介绍...

    常见数据结构和算法.zip

    数据结构和算法是计算机科学的基础,对于任何编程语言来说,理解和掌握它们都是至关重要的。本压缩包"常见数据结构和算法.zip"包含了针对C、C++、JAVA和Python的学习资源,旨在帮助大学生深入理解这些核心概念。以下...

Global site tag (gtag.js) - Google Analytics