基数排序的C++实现

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了基数排序的C++实现，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3059字，纯文字阅读大概需要5分钟。

内容图文

桶式排序　　

　　讲基数排序之前，先讲一下桶式排序，二者有较大关联。

　　桶式排序是一种排序方式，比如说有N个整数，这N个整数范围从1~M（0~M-1也行)，则可以创建一个数组count，大小为M，将所有元素先初始化为0，每个元素称为一个桶，这个数组有M个桶。然后将要排序的数字逐个读入，假设读到A这个数字，则数组对应的元素count[A]的值加1，即桶记录了落入该桶的数据的个数。读完后，按顺序输出非0的桶的index(count[index]为多少则输出多少次)，输出的数据则是排序后的数据。

　　举个例子，将9、3、1、1、0、5这六个数据进行桶式排序，则建立个数组，因为数据最大值为9，则可取M=10(数组大小为10），建立数组count[10]，读入数据，先读入9，则count[9]=1,读入3，则count[3]=1,……count[1]=2,依此类推……，读完后，count[10]={1,2,0,1,0,1,0,0,0,1},数组中有些元素是为0的，将不为0的数据对应的序号输出来，元素为多少则输出多少次，输出为0、1、1、3、5、9，即为正确排序。

基数排序

　　基数排序是桶式排序的推广，当数据范围太大时所需要的桶会太多，所以采用多趟的桶式排序。怎么个多趟法，方法是低位优先桶式排序（也有高位优先排序），假设有一串数据

73, 22, 93, 43, 55, 14, 28, 65, 39, 81 首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中： 0 1 　　81 2　　 22 3 　　73 93 43 4 　　14 5　　 55 65 6 7 8 　　28 9 　　39

第二步

接下来将这些桶子中的数值重新串接起来，成为以下的数列： 81, 22, 73, 93, 43, 14, 55, 65, 28, 39 接着再进行一次分配，这次是根据十位数来分配： 0 1 　　14 2 　　22 28 3 　　39 4 　　43 5 　　55 6 　　65 7 　　73 8 　　81 9 　　93

第三步

接下来将这些桶子中的数值重新串接起来，成为以下的数列： 14, 22, 28, 39, 43, 55, 65, 73, 81, 93 这时候整个数列已经排序完毕；如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。 ? C++代码实现

#include "pch.h"
#include <iostream>
using namespace std;

int maxbit(int data[], int n)//找出一组数据中的最大位数
{
    int count = 1;
    int d = 0;
    for (int i = 0; i < n; i++)
    {
        int temp = data[i];
        while (temp / 10 != 0)
        {
            count++;
            temp = temp / 10;
        }
        if (d < count)
            d = count;
        count = 1;
    }
    return d;
}
void radixsort(int data[], int n)//进行基数排序
{
    int d = maxbit(data, n);    //获取最大位数，即进行d次桶式排序
    int *tmp = new int[n];        //tmp指向的空间用来存放为每次桶式排序后的数据
    int *count = new int[10];    //count用来指向存放桶式排序后的落入各个桶的数字个数
    
    int radix = 1;
    int j, k;
    for (int i = 1; i <= d; i++)
    {
        for (int i = 0; i < 10; i++)
            count[i] = 0;            //每次分配前各个桶数据初始化为0
        for (int i = 0; i < n; i++)//进行d次排序
        {
            k = (data[i] / radix) % 10;//求出各个数据的某一位（个位、十位、百位…）是什么
            count[k]++;//对应的桶内数据加1，即桶内放了多少个数
        }
        for (j = 1; j < 10; j++)//目的是解决怎么将data数据按桶式顺序放到tmp所指空间中
            count[j] = count[j - 1] + count[j];
        for (int i = n-1; i>=0; i--)//把data里面的数据按排序后的顺序放入tmp所指空间，注意是从后面开始放数据
        {
            k = (data[i] / radix) % 10;
            tmp[count[k] - 1] = data[i];
            count[k]--;
        }
        for (int i = 0; i < n; i++)//把每次桶式排序后的数据给data
            data[i] = tmp[i];
        radix *= 10;
    }
    delete[] tmp;//释放内存
    delete[] count;//释放内存
}

int main()
{
    int data[10] = { 73, 22, 93, 43, 55, 14, 28, 65, 39, 81 };
    radixsort(data, 10);
    for (int i = 0; i < 10; i++)//输出排序后的数组数据
        cout << data[i] << " ";
    system("pause");
    return 0;
}

运行结果：

 

 

?

内容总结

以上是互联网集市为您收集整理的基数排序的C++实现全部内容，希望文章能够帮你解决基数排序的C++实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---