性时间排序-计数排序、基数排序和桶排序详解与编程实现

计数排序

计数排序假设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)
    {
   &nb

补充：软件开发 , C++ ,