`

【转】基数排序

 
阅读更多

转自: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)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达...

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

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

    Algorithm-基数排序

    基数排序(Radix Sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表示字符串(如电话号码)、日期等,基数排序并不限于整数。基数排序的名称来源...

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

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

    lemon-guide-基数排序

    在计算机科学中,基数排序(Radix Sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表示字符串(如电话号码)、浮点数等,基数排序也不是只能用于...

    python实现基数排序算法代码

    基数排序算法是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。具体实现时,从最低位开始,也就是个位数,然后是十位、百位等等,直到最高位。在每一趟排序中,使用的是...

    基数排序的Java实现方法RadixSort

    基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表示字符串、日期等,所以基数排序并不是只能用于整数。 基数排序的Java实现方法RadixSort,...

    基数排序_DataStructure-RadixSort.zip

    基数排序(Radix Sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表示字符串(如电话号码)、日期等,基数排序并不限于整数。通常用的排序算法...

    基数排序_Countingsort.zip

    基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表示字符串、算法中更确切地说是将数据中的每个数按照“基数”拆分成单个单位,然后从低位到...

    基数排序代码.docx

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

    基数排序算法.zip

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

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

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

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

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

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

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

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

    在探讨算法与数据结构的领域,Java编程语言提供了一种强大的工具来实现各种算法,其中包括基数排序和归并排序。基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较...

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

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

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

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

    java8中经典排序算法:插入排序、堆排序,选择排序、希尔排序,基数排序、

    基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。它的时间复杂度为O(nk),其中n是排序的数的个数,k是数的位数。当k不大时,基数排序的效率是很高的。 冒泡...

Global site tag (gtag.js) - Google Analytics