加载中…
个人资料
少师太
少师太
  • 博客等级:
  • 博客积分:0
  • 博客访问:51,425
  • 关注人气:20
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

Bin Sort——桶排序

(2009-07-31 10:39:40)
标签:

桶排序

杂谈

桶排序的原理和箱排序的基本原理是相同,在具体实现上稍微有点差别。

桶排序基本思想:是把[0...1]划分n个大小相同的子区间,每一子区间是一个桶,每一子区间是一个桶。然后将n个记录分配到各个桶中。因为关键字均匀的分布在[0...1)上的,所以一般不会有很多个记录落入同一个桶中。由于同一个桶中的记录关键字不尽相同,所以必须采用关键字比较的排序方法(通常用插入排序)对各个桶进行排序,然后依次将各非空桶中的记录连接收集起来即可。

桶排序算法
  伪代码算法为:
  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),用算
分析:
     这里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))。

5、基数排序:

要保证基数排序是正确的,就必须保证除第一趟外各趟排序是稳定的。

若排序文件不是以数组R形式给出,而是以单链表形式给相互(此时成为链式的基数排序)则可通过修改出队和入队函数使其表示箱子的链队,无须分配结点空间。

时间和空间复杂度的分析:

      基数排序的时间是线性的(即O(n))。
     基数排序所需的辅助存储空间为O(n+rd)。
     基数排序是稳定的。

(6)详细的C++代码:

3、基数排序

// Sorter.cpp : Defines the entry point for the console application.
//基数排序
#include "stdafx.h"
#include <iostream>
using namespace std;

void RadixSorter(int array[], int n, int d,int r)
{ //数组实现的基数排序,n为数组长度,d为排序码个数,r为基数
 int *TempArray=new int[n]; //辅助排序的临时数组

 int *count=new int[r]; //计数器,count[i]存储了第i个桶中的记录数

 int i,j,k;
 int Radix=1;    //用来取array[j]的第i位排序码
 for (i=1;i<=d;i++)   //分别对第i个排序码进行排序
 {
  for (j=0;j<r;++j)  //初始计数器均为0
   count[j]=0;
  for (j=0;j<n;++j)  //统计每个桶中的记录数
  {
   k=(array[j]/Radix)%r;//取array[j]的第i位排序码
   count[k]++;   //相应计数器加1
  }
  for(j=1;j<r;++j)   //将TempArray中的位置依次分配给r个桶
   count[j]=count[j-1]+count[j];

  for (j=n-1;j>=0;j--)  //将所有桶中的记录依次收集到TempArray中
  {
   k=(array[j]/Radix)%r; //去array[j]的第i为排序码
   count[k]--;    //从第k个桶取出一个记录,计数器减1
   TempArray[count[k]]=array[j];
  }
  for (j=0;j<n;j++)   //将临时数组中的内容复制到array中
   array[j]=TempArray[j];
  Radix*=r;
 }
}

 

int main(int argc, char* argv[])
{
 int len;
 int array[]={252,332,18,556,3,987,32,222};
 len=sizeof(array)/sizeof(int);  //数组的长度
// cout<<len;
 RadixSorter(array,len,3,10);
// int TempArray[100];

// TwoWayMergeSorter(array,TempArray,0,len-1);
 for (int i=0;i<len;++i)
 {
  cout<<array[i]<<" ";
 }

 cout<<endl;
// printf("Hello World!\n");
 return 0;
}
4、桶式排序

// Sorter.cpp : Defines the entry point for the console application.
//桶式排序
#include "stdafx.h"
#include <iostream>
using namespace std;

void BucketSorter(int array[], int n, int max)
{ //桶式排序,所有记录都位于区间[0,max)上
 int *TempArray=new int[n]; //临时数组

 int *count=new int[max]; //小于或等于i的元素个数

 int i;
 for (i=0;i<n;i++)
 {
  TempArray[i]=array[i];
 }
 //所有计数器初始都为0
 for(i=0;i<max;i++)
  count[i]=0;
 //统计每个取值出现的次数
 for (i=0;i<n;i++)
  count[array[i]]++;
 //统计小于等于i的元素个数
 for (i=1;i<max;i++)
  count[i]=count[i-1]+count[i];
 
 //从尾部开始按顺序输出有序序列,保证排序的稳定性
 for(i=n-1;i>=0;i--)
  array[--count[TempArray[i]]]=TempArray[i];
}

 

int main(int argc, char* argv[])
{
 int len;
 int array[]={2,3,8,5,3,9,3,2};
 len=sizeof(array)/sizeof(int);  //数组的长度
// cout<<len;
 BucketSorter(array,len,10);
// int TempArray[100];

// TwoWayMergeSorter(array,TempArray,0,len-1);
 for (int i=0;i<len;++i)
 {
  cout<<array[i]<<" ";
 }

 cout<<endl;
// printf("Hello World!\n");
 return 0;
}


 

 

 

 

 

 

 

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
前一篇:2009年07月31日
后一篇:2009年07月31日
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

    < 前一篇2009年07月31日
    后一篇 >2009年07月31日
      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有