`

【转】基数排序

阅读更多

转自:http://www.cppblog.com/shongbee2/archive/2009/04/24/80992.html

 

今天学了基数排序,据说他的时间复杂度也是O(n),他的思路就是:
没有计数排序那么理想,我们的数据都比较集中,都比较大,一般是4,5位。基本没有小的数据。
那我们的处理很简单,你不是没有小的数据嘛。我给一个基数,例如个位,个位都是[0-10)范围内的。先对他进行归类,把小的放上面,大的放下面,然后个位排好了,在来看10位,我们也这样把小的放上面,大的放下面,依次内推,直到最高位排好。那么不就排好了吗?我们只需要做d(基数个数)的循环就可以了。时间复杂度相当于O(d * n) 因为d为常量,例如5位数,d就是5.所以近似为O(n)的时间复杂度。这次自己写个案例:

最初的数据

排好个位的数据

排好十位的数据

排好百位的数据

981

981

725

129

387

753

129

387

753

955

753

456

129

725

955

725

955

456

456

753

725

387

981

955

456

129

387

981

这里只需循环3次就出结果了。

<!--[if !supportLists]-->3.       <!--[endif]-->但是注意,我们必须要把个位排好。但是个位怎么排呢?这个是个问题。书上说的是一叠一叠的怎么合并,我是没有理解的。希望知道的有高手教我一下。

我是用的一个计数排序来排各位的,然后排十位。效率应该也低不到哪里去。呵呵。。

思路就这样咯。奉上源代码:

 

#include <stdio.h>
#include <stdlib.h>

//计数排序,npRadix为对应的关键字序列,nMax是关键字的范围。npData是具体要
//排的数据,nLen是数据的范围,这里必须注意npIndex和npData对应的下标要一致
//也就是说npIndex[1] 所对应的值为npData[1]
int RadixCountSort(int* npIndex, int nMax, int* npData, int nLen)
{
    //这里就不用说了,计数的排序。不过这里为了是排序稳定
    
//在标准的方法上做了小修改。

    int* pnCount  = (int*)malloc(sizeof(int)* nMax);        //保存计数的个数
    for (int i = 0; i < nMax; ++i)
    {
        pnCount[i] = 0;
    }
    for (int i = 0; i < nLen; ++i)    //初始化计数个数
    {
        ++pnCount[npIndex[i]];
    }

    for (int i = 1; i < 10; ++i)  //确定不大于该位置的个数。
    {
        pnCount[i] += pnCount[i - 1];
    }

    int * pnSort  = (int*)malloc(sizeof(int) * nLen);    //存放零时的排序结果。

    
//注意:这里i是从nLen-1到0的顺序排序的,是为了使排序稳定。
    for (int i = nLen - 1; i >= 0; --i)
    {
        --pnCount[npIndex[i]];        
        pnSort[pnCount[npIndex[i]]] = npData[i];
    }

    for (int i = 0; i < nLen; ++i)        //把排序结构输入到返回的数据中。
    {
        npData[i] = pnSort[i];
    }
    free(pnSort);                        //记得释放资源。
    free(pnCount);
    return 1;
}

//基数排序
int RadixSort(int* nPData, int nLen)
{
    //申请存放基数的空间
    int* nDataRadix    = (int*)malloc(sizeof(int) * nLen);

    int nRadixBase = 1;    //初始化倍数基数为1
    bool nIsOk = false//设置完成排序为false

    
//循环,知道排序完成
    while (!nIsOk)
    {
        nIsOk = true;
        nRadixBase *= 10;
        for (int i = 0; i < nLen; ++i)
        {
            nDataRadix[i] = nPData[i] % nRadixBase;
            nDataRadix[i] /= nRadixBase / 10;
            if (nDataRadix[i] > 0)
            {
                nIsOk = false;
            }
        }
        if (nIsOk)        //如果所有的基数都为0,认为排序完成,就是已经判断到最高位了。
        {
            break;
        }
        RadixCountSort(nDataRadix, 10, nPData, nLen);
    }

    free(nDataRadix);

    return 1;
}

int main()
{
    //测试基数排序。
    int nData[10] = {123,5264,9513,854,9639,1985,159,3654,8521,8888};
    RadixSort(nData, 10);
    for (int i = 0; i < 10; ++i)
    {
        printf("%d ", nData[i]);
    }
    printf("\n");

    system("pause");
    return 0;
}
分享到:
评论

相关推荐

    C++写基数排序算法

    基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。在C++中实现基数排序,主要涉及到数组、计数排序以及位操作等技术。以下是关于基数排序及其C++实现的详细解释...

    数据结构基数排序

    数据结构中的基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序并不是只能用于整数...

    Radix Sort (基数排序)排序算法

    ### Radix Sort (基数排序) 排序算法详解 #### 一、算法介绍与应用场景 基数排序(Radix Sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达...

    利用递归算法实现的基数排序算法

    基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。递归算法则是一种解决问题的方法,它解决问题的每一个子问题都是原问题的缩小版,直到子问题简单到可以直接...

    对10进制数进行基数排序 数据结构

    ### 对10进制数进行基数排序的数据结构与算法实现 #### 1. 基数排序概述 基数排序是一种非比较型整数排序算法,它通过整数的各位数字来分配进桶的方式来进行排序。该算法对于固定大小的整数特别有效。基数排序的...

    基数排序代码.docx

    基数排序(Radix Sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表示字符串(如将数字转换为字符串形式),所以基数排序也可以很自然地扩展到...

    基数排序算法.zip

    基数排序是一种非比较型整数排序算法,它的原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。这种算法是通过分配、收集和再分配的步骤来实现的,它不依赖于元素之间的比较,而是依赖于数字的位数。这种...

    C++实现基数排序(源代码)

    ### C++实现基数排序 #### 一、基数排序概述 基数排序是一种非比较型的整数排序算法。它通过对整数的每一位进行排序来达到整体序列的有序化。该算法的特点在于它不是通过元素间的相互比较来进行排序,而是通过按...

    Java实现基数排序算法(源代码)

    ### Java实现基数排序算法 #### 实现原理 基数排序是一种非常高效的非比较型整数排序算法,它通过按数字的各个位数进行排序来实现序列的整体有序化。该算法的关键在于能够有效地处理多位数,避免了传统的两两比较...

    基数排序介绍和java代码实现

    基数排序是一种非比较型整数排序算法,它的核心在于将数字按位进行处理,从低位到高位逐位进行排序。这种排序方式适用于处理包含整数或者可以转换为整数形式的数据,如字符串。基数排序的关键在于“计数排序”...

    链表基数排序的存储空间效率优化.pptx

    ### 链表基数排序的存储空间效率优化 #### 一、优化桶结构,降低空间消耗 在链表基数排序中,桶结构的选择对于优化存储空间有着至关重要的作用。优化桶结构可以从以下几个方面入手: 1. **基于哈希表的优化桶结构...

    对时间进行基数排序,输入的是整数格式、输出的是字符串形式

    ### 时间整数格式基数排序及转换为字符串形式 在计算机科学中,基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数进行比较。基数排序通常用于那些不是通过比较元素大小来...

    算法与数据结构,Java基数排序,归并排序,利用栈将四则表达式中缀转换为后缀并计算_Arithmetic.zip

    算法与数据结构,Java基数排序,归并排序,利用栈将四则表达式中缀转换为后缀并计算_Arithmetic

    数据结构-排序PPT课件.pptx

    本资源是关于数据结构中排序算法的PPT课件,全文共118页,详细介绍了排序的概念、内部排序和外部排序、内部排序方法的分类、插入排序、快速排序、堆排序、归并排序、基数排序等内容。 1. 排序的概念:排序是计算机...

    算法与数据结构实验五 (快速、堆、基数)排序算法的设计

    LSD法从最低位开始,按照每位的数值大小将元素分配到不同的桶中,然后收集回原位置,依次处理高位,直到所有位处理完,数组就按基数排序好了。基数排序的时间复杂度为O(kn),其中k是数字的最大位数,n是元素数量,...

    JS实现的计数排序与基数排序算法示例

    计数排序与基数排序是两种非比较型排序算法。计数排序适用于一定范围内的整数排序,在特定条件下,它比基于比较的排序算法如快速排序、归并排序等拥有更好的时间复杂度。基数排序则是一种借助“基数”概念来按位数...

    数据结构算法课程设计-汽车牌照的排序与查找问题

    首先,对于排序部分,选择了基数排序这一非比较型整数排序算法。基数排序的基本思想是根据每位数字分别排序,从低位到高位,逐次进行。在本案例中,由于车牌号包括汉字、字母和数字,所以需要将汉字转换为对应的拼音...

    汽车牌照的排序与查找问题-数据结构与算法课程设计报告

    程序设计上,主要包括以下几个函数:`main()`作为主函数,`Setlist()`用于添加车辆,`Distribute()`和`Collect()`分别用于基数排序的分配和收集阶段,`find()`执行二分查找,`menu()`提供用户交互界面,`print()`...

    八种常见排序算法总结(转)

    基数排序是一种基于分布的排序算法,它的思想是将待排序的数组根据关键字的每一位进行排序,首先根据低位的关键字进行排序,然后根据高位的关键字进行排序。基数排序的时间复杂度最好的情况下为 O(nk),最坏的情况下...

Global site tag (gtag.js) - Google Analytics