标签: radix-sort

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

编辑:这不是作业.

我还在学习Haskell,并编写了以下基数排序函数.它似乎工作正常,但问题是它相当于内存效率低下.如果使用ghc编译,则内存大小超过500MB,输入列表大小为10000个元素.

所以我想问你如何改进以下算法/代码,使其在速度和内存方面更有效率.什么是最好的起点？

import System.Random

-- radixsort for positive integers. uses 10 buckets
radixsort :: [Int] -> [Int]
radixsort [] = []
radixsort xs =
    -- given the data, get the number of passes that are required for sorting
    -- the largest integer
    let maxPos = floor ((log (fromIntegral (foldl max 0 xs)) / log 10) + 1)

        -- start sorting from digit on position 0 (lowest position) to position 'maxPos'
        radixsort' ys pos
         | pos < 0   = ys
         | …

我正在阅读算法第2版的介绍,并且有一个问题说我们可以排序n个整数,它们在线性时间内介于0和n ³ -1 之间.我正在考虑IBM的基数排序方法.我从最低有效数字开始,相对于最低有效数字分开数字,然后排序,然后相对于下一个最低有效数字分开,依此类推.每次分离需要O(n)次.但我有一个疑问,例如,如果其中一个数字由n个数字组成,那么算法需要O(1*n + 2*n + ... + n*n)= O(n ²)时间,对吗？我们能否确保数字少于n位数,或者是否有人可以提出另一个问题提示？谢谢

我正在探索以下算法:

1. 计数排序
2. 基数排序
3. 铲斗排序

我知道这三个都能够在最佳情况下以线性时间运行,但是我很难理解这些情况何时发生,除了计算排序的情况.

以下是我对计数排序的理解,以及如果可能的话我希望如何回答其他两种算法:

当您希望排序的信息之间没有大的间隙时,计数排序以线性时间运行.例如,1,10 ^ 5和545等将创建一个大型数组并且使用内存和遍历效率不高所以这将是使用计数排序的"更糟糕的情况",因此最好的情况是差距很小.

如果有人能帮我理解线性时间发生时基数和桶排序最佳情况的条件,我将不胜感激.

从具有n位数的int中获取单个数字以在基数排序算法中使用的最佳方法是什么？我想知道在C/C++中是否有一种特别好的方法,如果不是什么是一般的最佳解决方案？

编辑:只是为了澄清,我正在寻找一个解决方案,而不是将其转换为字符串并将其视为一个数字数组.

我正在尝试实现美式桶排序。维基百科说：“首先计算每个垃圾箱中掉落的物体数量，然后将每个物体放入其桶中。”

第二阶段，将对象放入适当的桶中时，是否需要使用辅助数组？有没有办法通过在线性时间内交换数组元素来做到这一点？

我真的很困惑“就地”MSD基数排序算法：

然后使用下一个数字递归处理每个 bin，直到所有数字都用于排序。

我很困惑，因为在我看来递归意味着 O(n) 堆栈空间，其中n是最长字符串的长度（位数），对吗？

在我看来，避免堆栈溢出的唯一方法是使用堆空间——但是根据任何定义，算法不再是“就地”。

那么，如何就地完成就地 MSD 基数排序呢？

我不确定为什么会使用LSD基数排序.

MSD的优点:

1. 它可以处理可变长度的字符串
2. 它并不总是需要扫描整个字符串(它可以更快地决定订单)
3. 可以使用插入排序来规避计数排序的缺点.

我想对整数进行排序，并且我知道基数排序对此非常有用。任何此类的库实现？

好的,所以我必须为无符号整数和浮点数创建基数排序.我的无符号整数版本可以正常工作,但我在使浮点值工作时遇到了一些麻烦.基本上,它按浮点数的整数值对数组的值进行排序,但不会根据小数值对其进行排序.(例如36.65234将出现在36.02311之前,如果它出现在未排序的数组中)这个代码段是我进行操作和屏蔽的地方,我很确定我的问题出在哪里.

/* For loop to create bin */
for(int i=0; i<n; i++){
    temp_int = (((unsigned int)(list[i]))>>bitwise)&0xff;
    bin[temp_int] = bin[temp_int]+1;
  }

  /*For loop to get map */
  for (int i=0; i<256; i++) {
    map[i+1] = bin[i]+count;
    count = map[i+1];
  }

  /* For loop to copy "sorted" values into other array */
  for (int i=0; i<n; i++) {
    temp_int = (((unsigned int)(list[i]))>>bitwise)&0xff;
    int buf_loc = map[temp_int];
    temp_arr[buf_loc] = list[i];
    map[temp_int] = map[temp_int]+1;
  }

提前致谢!