频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
性时间排序-计数排序、基数排序和桶排序详解与编程实现
2013-03-29 08:12:48      个评论      
收藏   我要投稿

计数排序

计数排序假设n个输入元素中的每一个都是介于0到k之间的整数。此处k为某个整数(输入数据在一个小范围内)。

 

算法思想

计数排序的基本思想是对每一个输入元素x,确定出小于x的元素的个数。然后再将x直接放置在它在最终输出数组中的位置上。

 


由于数组中可能有相等的数,在处理时需要注意。

 


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


算法总时间Θ(k + n)。当k=O(n)时,计数排序的运行时间是Θ(n)。

空间复杂度是O(n+k)。需要两个辅助数组:存放排序结果的数组B[n],存放临时结果的C[k]。


计数排序是稳定的排序算法。

 

 

编程实现(CPP)

[cpp] 
//计数排序-《算法导论(第二版)》P98 8.2计数排序  
//Author:江南烟雨  
//E-Mail:xiajunhust@gmail.com  
 
#include <iostream>  
#include <cstdlib>  
 
using namespace std; 
 
void CountSort(int *a,const int num,int *result) 

    int MaxVal = -99999; 
    for(int i = 0;i < num;++i) 
    { 
        if(MaxVal < *(a + i)) 
            MaxVal = *(a + i); 
    } 
    int *tempResult = new int[MaxVal + 5];//记录中间结果  
    for(int i = 0;i < MaxVal  + 5;++i) 
        *(tempResult + i) = 0; 
    //result[i]记录数组中值等于i的元素的个数  
    for(int i = 0;i < num;++i) 
        *(tempResult + *(a + i)) = *(tempResult + *(a + i)) + 1; 
    //result[i]记录数组中值小于等于i的元素的个数  
    for(int i = 1;i < MaxVal + 5;++i) 
        *(tempResult + i) = *(tempResult + i) + *(tempResult + i - 1); 
    //注意,数组中可能存在相等的元素  
    //将数组中各元素直接放入正确的位置  
    for (int i = num - 1;i >= 0;--i) 
    { 
        *(result + *(tempResult + *(a + i))) = *(a + i); 
        *(tempResult + *(a + i)) = *(tempResult + *(a + i)) - 1; 
    } 
 
    delete[] tempResult; 

 
int main() 

     int num = 7; 
    int *a = new int[num]; 
    for(int i = 0;i < num;++i) 
        *(a + i) = rand(); 
 
    cout << "Before sort: " << endl; 
    for(int i = 0;i < num;++i) 
        cout << *(a + i) << " "; 
    cout << endl; 
 
    int *result = new int[num + 5]; 
 
    CountSort(a,num,result); 
 
    cout << "After sort: " << endl; 
    for(int i = 1;i <= num;++i) 
        cout << *(result + i) << " "; 
    cout << endl; 
 
    delete[] a; 
    delete[] result; 

//计数排序-《算法导论(第二版)》P98 8.2计数排序
//Author:江南烟雨
//E-Mail:xiajunhust@gmail.com

#include <iostream>
#include <cstdlib>

using namespace std;

void CountSort(int *a,const int num,int *result)
{
 int MaxVal = -99999;
 for(int i = 0;i < num;++i)
 {
  if(MaxVal < *(a + i))
   MaxVal = *(a + i);
 }
 int *tempResult = new int[MaxVal + 5];//记录中间结果
 for(int i = 0;i < MaxVal  + 5;++i)
  *(tempResult + i) = 0;
 //result[i]记录数组中值等于i的元素的个数
 for(int i = 0;i < num;++i)
  *(tempResult + *(a + i)) = *(tempResult + *(a + i)) + 1;
 //result[i]记录数组中值小于等于i的元素的个数
 for(int i = 1;i < MaxVal + 5;++i)
  *(tempResult + i) = *(tempResult + i) + *(tempResult + i - 1);
 //注意,数组中可能存在相等的元素
 //将数组中各元素直接放入正确的位置
 for (int i = num - 1;i >= 0;--i)
 {
  *(result + *(tempResult + *(a + i))) = *(a + i);
  *(tempResult + *(a + i)) = *(tempResult + *(a + i)) - 1;
 }

 delete[] tempResult;
}

int main()
{
  int num = 7;
 int *a = new int[num];
 for(int i = 0;i < num;++i)
  *(a + i) = rand();

 cout << "Before sort: " << endl;
 for(int i = 0;i < num;++i)
  cout << *(a + i) << " ";
 cout << endl;

 int *result = new int[num + 5];

 CountSort(a,num,result);

 cout << "After sort: " << endl;
 for(int i = 1;i <= num;++i)
  cout << *(result + i) << " ";
 cout << endl;

 delete[] a;
 delete[] result;
}

 

基数排序

 

算法思想
基数排序是从低位到高位依次对所有的数进行排序。如果所有的数最高位数是d,那么先按最低有效位数字进行排序,得到一个结果。然后往高位重复这个过程。

需要注意的是,按位排序必须是稳定的排序算法。经常采用的是计数排序。

 


编程实现(CPP)

[cpp]
//基数排序  
//《算法导论(第二版)》P100 8.3 基数排序  
//Author:江南烟雨  
//E-Mail:xiajunhust@gmail.com  
 
#include <iostream>  
#include <cstdlib>  
#include <ctime>  
 
using namespace std; 
 
//得到某个整数第i位的数值  
int getDigitNun(int a,int digit); 
//按位排序  
void DigitSort(int *a,int n,int digit,int *result); 
//基数排序算法  
void RadixSort(int *a,int n,int d); 
 
int main() 

    int n = 7,i; 
    int *a = new int[n]; 
    srand(time(NULL)); 
    for(i = 0;i < n;++i) 
        *(a + i) = rand(); 
    //判断最大的数的位数  
    int MaxVal = -1,d = 0; 
    cout << "Before sort : " << endl; 
    for(i = 0;i < n;++i) 
    { 
        cout << *(a + i) << " "; 
        MaxVal = MaxVal < *(a + i) ? *(a + i) : MaxVal; 
    } 
    cout << endl; 
    while(MaxVal > 0) 
    { 
        ++d; 
        MaxVal /= 10; 
    } 
 
    RadixSort(a,n,d); 
 
    cout << "After sort : " << endl; 
    for(i = 0;i < n;++i) 
        cout << *(a + i) << " "; 
    cout << endl; 

 
//基数排序算法  
void RadixSort(int *a,int n,int d) 

    int *result = new int[n + 5]; 
    //循环执行按位排序操作  
    for (int i =1;i <= d;++i) 
    { 
        DigitSort(a,n,i,result); 
        for (int j = 0;j < n;++j) 
        { 
            *(a + j) = *(result + j + 1); 
        } 
    } 
 
    delete[] result; 

 
//得到某个整数第i位的数值  
int getDigitNun(int a,int digit) 

    while(--digit) 
    { 
        a /= 10; 
    } 
 
    return a % 10; 

 
//按位排序  
//这里采用选择排序  
void DigitSort(int *a,int n,int digit,int *result) 

    //记录中间结果  
    const int num = 15; 
    int *tempResult = new int[num]; 
    for(int i = 0;i < num;++i) 
        *(tempResult + i) = 0;//初始化  
 
    //tempResult[i]记录数组中等于i的数的个数  
    for(int i = 0;i < n;++i) 
        *(tempResult + getDigitNun(*(a + i),digit)) = *(tempResult + getDigitNun(*(a + i),digit)) + 1; 
 
    //tempResult[i]记录数组中小于等于i的数的个数  
    for(int i = 1;i < num;++i) 
        *(tempResult + i) = *(tempResult + i) + *(tempResult + i - 1); 
 
    //将个元素直接放入正确的位置  
    for(int i = n - 1;i >= 0;--i) 
    { 
        *(result + *(tempResult + getDigitNun(*(a + i),digit))) = *(a + i); 
        *(tempResult + getDigitNun(*(a + i),digit)) = *(tempResult + getDigitNun(*(a + i),digit)) - 1; 
    } 
 
    delete[] tempResult; 

//基数排序
//《算法导论(第二版)》P100 8.3 基数排序
//Author:江南烟雨
//E-Mail:xiajunhust@gmail.com

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

//得到某个整数第i位的数值
int getDigitNun(int a,int digit);
//按位排序
void DigitSort(int *a,int n,int digit,int *result);
//基数排序算法
void RadixSort(int *a,int n,int d);

int main()
{
 int n = 7,i;
 int *a = new int[n];
 srand(time(NULL));
 for(i = 0;i < n;++i)
  *(a + i) = rand();
 //判断最大的数的位数
 int MaxVal = -1,d = 0;
 cout << "Before sort : " << endl;
 for(i = 0;i < n;++i)
 {
  cout << *(a + i) << " ";
  MaxVal = MaxVal < *(a + i) ? *(a + i) : MaxVal;
 }
 cout << endl;
 while(MaxVal > 0)
 {
  ++d;
  MaxVal /= 10;
 }

 RadixSort(a,n,d);

 cout << "After sort : " << endl;
 for(i = 0;i < n;++i)
  cout << *(a + i) << " ";
 cout << endl;
}

//基数排序算法
void RadixSort(int *a,int n,int d)
{
 int *result = new int[n + 5];
 //循环执行按位排序操作
 for (int i =1;i <= d;++i)
 {
  DigitSort(a,n,i,result);
  for (int j = 0;j < n;++j)
  {
   *(a + j) = *(result + j + 1);
  }
 }

 delete[] result;
}

//得到某个整数第i位的数值
int getDigitNun(int a,int digit)
{
 while(--digit)
 {
  a /= 10;
 }

 return a % 10;
}

//按位排序
//这里采用选择排序
void DigitSort(int *a,int n,int digit,int *result)
{
 //记录中间结果
 const int num = 15;
 int *tempResult = new int[num];
 for(int i = 0;i < num;++i)
  *(tempResult + i) = 0;//初始化

 //tempResult[i]记录数组中等于i的数的个数
 for(int i = 0;i < n;++i)
  *(tempResult + getDigitNun(*(a + i),digit)) = *(tempResult + getDigitNun(*(a + i),digit)) + 1;

 //tempResult[i]记录数组中小于等于i的数的个数
 for(int i = 1;i < num;++i)
  *(tempResult + i) = *(tempResult + i) + *(tempResult + i - 1);

 //将个元素直接放入正确的位置
 for(int i = n - 1;i >= 0;--i)
 {
  *(result + *(tempResult + getDigitNun(*(a + i),digit))) = *(a + i);
  *(tempResult + getDigitNun(*(a + i),digit)) = *(tempResult + getDigitNun(*(a + i),digit)) - 1;
 }

 delete[] tempResult;
}


时间复杂度和空间复杂度分析
给定n个d位数,每一个数位可能取值中数是k,如果所用的稳定的按位排序时间复杂度是Θ(n+k),基数排序时间复杂度是Θ(d(n+k))。空间复杂度O(n+k)。

当d为常数,k=O(n)时,基数排序有线性时间复杂度。

 


关于如何将每个关键字分解成若干数位方面,有另外一个定理:

给定n个b维数和任何正整数r<=b,基数排序能在Θ((b/r)(n+2^r))时间内对这些数进行排序。

这里,对一个值r<=b,将每个关键字看做是有d = floor(b/r)个数字,每个数字含有r位,再进行计数排序。

上述式子可以推导得到Θ(n)复杂度。

 


但是这并不意味着基数排序比基于比较的排序算法比如快排更好!因为隐含在记号中的常数因子是不同的。哪一个排序算法更好取决于底层机器的实现特性,比如快排同==排通常可以更有效地利用硬件缓存。同时还取决于输入数据。而且利用计数排序作为中间稳定排序不是原地排序。

 


桶排序
当输入数据符合均匀分布时,即可以以线性期望时间运行。即使输入不满足线性关系,桶排序也仍然可以以线性时间运行。只要输入满足这样一个性质,即各个桶尺寸的平方和与总的元素数呈线性关系。

 


桶排序的思想:

将区间[0,1)分成n个相同大小的子区间,或称为桶。然后将n个输入元素分布到各个桶中去。每个桶中的元素用一个链表来存储。

 

 

编程实现(CPP)

[cpp] 
//桶排序  
//《算法导论(第二版)》P102 8.4 桶排序  
//Author:江南烟雨(2013-03027)  
//E-Mail:xiajunhust@gmail.com  
 
#include <iostream>  
#include <cstdlib>  
#include <ctime>  
#include <cmath>  
 
using namespace std; 
 
//桶中链表节点数据结构  
typedef struct StructLinkNode{ 
    double elem; 
    struct StructLinkNode *next; 
}LinkNode,*LinkNodePtr; 
 
//桶排序  
void BucketSort(double *a,int n); 
//删除一条链表  
void deleteLinkList(LinkNodePtr head); 
 
int main() 

    srand(time(NULL)); 
    int n = 8; 
    double *a = new double[n]; 
    for(int i = 0;i < n;++i) 
        *(a + i) = rand() * 1.0 / RAND_MAX; 
 
    cout << "Before sort : " << endl; 
    for(int i = 0;i < n;++i) 
        cout << *(a + i) << "  "; 
    cout << endl; 
 
    BucketSort(a,n); 
 
    cout << "After sort : " << endl; 
    for(int i = 0;i < n;++i) 
        cout << *(a + i) << "  "; 
    cout << endl; 

 
//桶排序  
void BucketSort(double *a,int n) 

    //存放链表的数组  
    LinkNodePtr *linkListArr = new LinkNodePtr[n]; 
    //初始化  
    for (int i = 0;i < n;++i) 
    { 
        linkListArr[i] = new LinkNode; 
        linkListArr[i]->elem = -1; 
        linkListArr[i]->next = NULL; 
    } 
 
    //将n个输入元素依次放入n个桶中  
    for (int i = 0;i < n;++i) 
    { 
        LinkNodePtr newNode = new LinkNode; 
        newNode->elem = *(a + i); 
        newNode->next = NULL; 
 
        //将新元素插入对应桶的链表的正确位置  
        int index = floor(n * *(a + i)); 
        LinkNodePtr loopPtr = linkListArr[index]->next; 
        LinkNodePtr prevPtr = linkListArr[index]; 
        while(loopPtr != NULL && *(a + i) > loopPtr->elem) 
        { 
            prevPtr = loopPtr; 
            loopPtr = loopPtr->next; 
        } 
        newNode->next = loopPtr; 
        prevPtr->next = newNode; 
    } 
 
    int count = 0; 
    for (int i = 0;i < n;++i) 
    { 
        LinkNodePtr loopPtr = linkListArr[i]->next; 
        while(loopPtr != NULL) 
        { 
            *(a + count) = loopPtr->elem; 
            ++count; 
            loopPtr = loopPtr->next; 
        } 
    } 
 
    for (int i = 0;i < n;++i) 
        deleteLinkList(linkListArr[i]); 

 
//删除一条链表  
void deleteLinkList(LinkNodePtr head) 

    if (NULL == head) 
    { 
        return; 
    } 
    deleteLinkList(head->next); 
    delete head; 

//桶排序
//《算法导论(第二版)》P102 8.4 桶排序
//Author:江南烟雨(2013-03027)
//E-Mail:xiajunhust@gmail.com

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>

using namespace std;

//桶中链表节点数据结构
typedef struct StructLinkNode{
 double elem;
 struct StructLinkNode *next;
}LinkNode,*LinkNodePtr;

//桶排序
void BucketSort(double *a,int n);
//删除一条链表
void deleteLinkList(LinkNodePtr head);

int main()
{
 srand(time(NULL));
 int n = 8;
 double *a = new double[n];
 for(int i = 0;i < n;++i)
  *(a + i) = rand() * 1.0 / RAND_MAX;

 cout << "Before sort : " << endl;
 for(int i = 0;i < n;++i)
  cout << *(a + i) << "  ";
 cout << endl;

 BucketSort(a,n);

 cout << "After sort : " << endl;
 for(int i = 0;i < n;++i)
  cout << *(a + i) << "  ";
 cout << endl;
}

//桶排序
void BucketSort(double *a,int n)
{
 //存放链表的数组
 LinkNodePtr *linkListArr = new LinkNodePtr[n];
 //初始化
 for (int i = 0;i < n;++i)
 {
  linkListArr[i] = new LinkNode;
  linkListArr[i]->elem = -1;
  linkListArr[i]->next = NULL;
 }

 //将n个输入元素依次放入n个桶中
 for (int i = 0;i < n;++i)
 {
  LinkNodePtr newNode = new LinkNode;
  newNode->elem = *(a + i);
  newNode->next = NULL;

  //将新元素插入对应桶的链表的正确位置
  int index = floor(n * *(a + i));
  LinkNodePtr loopPtr = linkListArr[index]->next;
  LinkNodePtr prevPtr = linkListArr[index];
  while(loopPtr != NULL && *(a + i) > loopPtr->elem)
  {
   prevPtr = loopPtr;
   loopPtr = loopPtr->next;
  }
  newNode->next = loopPtr;
  prevPtr->next = newNode;
 }

 int count = 0;
 for (int i = 0;i < n;++i)
 {
  LinkNodePtr loopPtr = linkListArr[i]->next;
  while(loopPtr != NULL)
  {
   *(a + count) = loopPtr->elem;
   ++count;
   loopPtr = loopPtr->next;
  }
 }

 for (int i = 0;i < n;++i)
  deleteLinkList(linkListArr[i]);
}

//删除一条链表
void deleteLinkList(LinkNodePtr head)
{
 if (NULL == head)
 {
  return;
 }
 deleteLinkList(head->next);
 delete head;
}

时间和空间复杂度分析

时间复杂度是O(n)。

空间复杂度是O(n)。需要一个辅助数组来存放桶(链表)。

 


即使输入不满足均匀分布,桶排序也仍然可以以线性时间运行,只要输入满足这样一个条件:各个桶尺寸的平方和与总的元素呈线性关系。

 


桶排序是稳定排序算法。

 

点击复制链接 与好友分享!回本站首页
相关TAG标签 基数 时间
上一篇:c++例题 构造函数(一)
下一篇:C++中宏的使用技巧
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站