标签: radix-sort

可能重复:
长度为N的数组可以包含值1,2,3 ... N ^ 2.是否有可能在O(n)时间内排序？

给定n范围内的数字[0,n^2 -1]我们如何在O(n)运行时间对它们进行排序？

我有一种感觉,解决方案涉及radix sort,但我仍然缺少一些东西.

该n数字是整数.

有任何想法吗 ？

备注:不是作业!

问候

我有一个带有float类型字段的数据结构.这些结构的集合需要按浮点值进行排序.是否存在基数排序实现.

如果没有,是否有快速访问指数,符号和尾数的方法.因为如果你最后一次在尾数,指数和指数上对浮点数进行排序.你在O(n)中排序浮点数.

我试图通过创建一个程序来改进我的C++,该程序将需要1到10 ^ 6之间的大量数字.将在每次传递中存储数字的存储桶是一个节点数组(其中node是我创建的包含值和下一个节点属性的结构).

根据最低有效值将数字排序到桶中后,我将一个桶的末尾指向另一个桶的开头(这样我可以快速获取存储的数字而不会中断订单).我的代码没有错误(编译或运行时),但我已经找到了解决剩下的6次迭代的问题(因为我知道数字的范围).

我遇到的问题是,最初这些数字是以int数组的形式提供给radixSort函数的.在排序的第一次迭代之后,数字现在存储在结构数组中.有没有什么方法可以重新编写我的代码,以便我只有一个for循环进行7次迭代,或者我需要一个for循环,它将运行一次,而另一个循环下面将运行6次,然后返回完全排序清单？

#include <iostream>
#include <math.h>
using namespace std;

struct node
{
    int value;
    node *next; 
};

//The 10 buckets to store the intermediary results of every sort
node *bucket[10];
//This serves as the array of pointers to the front of every linked list
node *ptr[10];
//This serves as the array of pointer to the end of every linked list
node *end[10];
node *linkedpointer;
node *item;
node *temp;

void append(int value, int n)
{
    node *temp; 
    item=new …

我想用队列创建一个基数排序实现.

我无法弄清楚我的代码的哪个部分有问题或我应该阅读哪些资源.我的代码可能完全错误,但这是我的实现没有任何帮助(我尚未采用数据结构和算法课程).

我创建了一个函数,但它没有用.在做研究时,我看到了一些代码示例,但对我来说似乎更复杂.

首先,我想找到所有整数的最低有效位数 然后在其下标匹配的队列元素中对它们进行排序, 然后在排序后将所有队列复制到第11个队列元素的末尾.在第11个队列元素中再次进行此排序,直到达到最高位数.

我能找到最不重要的数字.并根据这个数字排序.但是,我无法分析其他数字.例如; 我可以排序1,2,4,5,3,但是当排序2位或更多位数时,它会失败......

我希望,我很清楚并简要地解释了我的问题.

// My function declaration
// Pre: arrInts holds the linked list of integers which are going to be sort.
// Post: queue will return result and its 11th element should hold sorted integers in
//       that queue
queue_node_t * radixSort(const queue_node_t *arrInts, queue_t *queue[], int size){
    queue_node_t *curNodep = arrInts; // Node to be checked
    int i, curNum = curNodep->element.key;
    if(curNodep == NULL){
        // If there …

Timsort,Quicksort和Mergesort等算法主宰了" 真实世界 "的排序方法.这些比较类型的情况非常实用 - 它们已被证明是各种环境中性能最高,最稳定,多用途的排序算法.

但是,似乎我们在计算机上排序的几乎所有内容都是可数/部分排序的.数字,字符,字符串,甚至函数都适用于某些有意义的非比较排序方法.这里的候选人是Radix排序.一般情况下,它会比O(n*log(n))表现得更快,在许多情况下以大范围击败n*log(n)的理论比较排序限制,复杂度为O(K*n) - K是表示特定项目所需的位数.

是什么赋予了？

我对Web上的许多python radix实现的排序感到非常沮丧.

它们一直使用10的基数,并通过除以10的幂或得到数字的log10来得到它们迭代的数字的数字.这是非常低效的,因为与位移相比,log10不是特别快的操作,这几乎快了100倍!

更高效的实现使用256的基数并逐字节地对数字进行排序.这允许使用可笑的快速位运算符完成所有"字节获取".不幸的是,似乎绝对没有人在python中实现了使用位运算符而不是对数的基数排序.

因此,我亲自动手并想出了这只野兽,它的运行速度大约是小型阵列的一半,并且在大型阵列上的运行速度几乎一样快(例如len大约10,000,000):

import itertools

def radix_sort(unsorted):
    "Fast implementation of radix sort for any size num."
    maximum, minimum = max(unsorted), min(unsorted)

    max_bits = maximum.bit_length()
    highest_byte = max_bits // 8 if max_bits % 8 == 0 else (max_bits // 8) + 1

    min_bits = minimum.bit_length()
    lowest_byte = min_bits // 8 if min_bits % 8 == 0 else (min_bits // 8) + 1

    sorted_list = unsorted
    for offset in xrange(lowest_byte, highest_byte):
        sorted_list = radix_sort_offset(sorted_list, offset)

    return sorted_list

def …

给定N数范围Eg [1到100],按数字顺序对数字进行排序(即)对于数字1到100,排序的输出伤口为1 10 100 11 12 13...19 2 20 21 ..... 99

这就像Radix Sort一样,但只是数字按照与正常Radix Sort相反的顺序排序.

我试图将每个数字中的所有数字存储为链接列表,以便更快地操作,但这会导致很大的空间复杂度.

我需要一个有问题的工作算法.

从所有答案中,"转换为字符串"是一种选择,但是没有其他方法可以做到这一点吗？还可以给出如上所述的用于排序字符串的算法.

根据我的理解,R的order()方法默认使用基数排序.情况并非总是如此(见新闻),但Matt Dowle提出了这个演示文稿,因为基数排序在经验上表现良好.

我的问题是,为什么radix排序比实际中的其他排序算法更好？维基百科对基数排序没有强有力的理由.另外,为什么其他流行的语言/工具如Python和pandas默认不使用基数排序,如果它真的是最好的排序算法？

给定一个长度为N的数组.它可以包含范围从1到N ^ 2(N平方)的值,包括值,值是整数.是否可以在O(N)时间内对此数组进行排序？如果可能怎么样？

编辑:这不是作业.

我在C++中编写了一个间接基数排序算法(通过间接,我的意思是它返回项目的索引):

#include <algorithm>
#include <iterator>
#include <vector>

template<class It1, class It2>
void radix_ipass(
    It1 begin, It1 const end,
    It2 const a, size_t const i,
    std::vector<std::vector<size_t> > &buckets)
{
    size_t ncleared = 0;
    for (It1 j = begin; j != end; ++j)
    {
        size_t const k = a[*j][i];
        while (k >= ncleared && ncleared < buckets.size())
        { buckets[ncleared++].clear(); }
        if (k >= buckets.size())
        {
            buckets.resize(k + 1);
            ncleared = buckets.size();
        }
        buckets[k].push_back(size_t());
        using std::swap; swap(buckets[k].back(), *j);
    }
    for (std::vector<std::vector<size_t> >::iterator
        j …