1回答
在区间n整数中有[0,n^c]整数，其中c是正整数。
我可以用哪种算法在线性时间对这些整数进行排序？
我确实看过RadixSort的问题如下:给定最长的数字最多有c_nlogn位数，那么RadixSort不会在O(n_logn)时间内运行吗？
浏览 1提问于2017-06-10得票数 0
回答已采纳
1回答
计数排序的稳定性
、、
我用python实现了一个计数排序算法。我看到计数排序是稳定的，因为它保留了元素在原始数组中的顺序。你认为下面的实现是稳定的吗？
def countingsort(A,n):
C = [0]*n
B = [0]*n
# the value of A[i] becomes the index for counting
# C now stores the no. of occurences of element A[i] in A
for i in A:
C[i] = C[i] + 1
浏览 4提问于2015-10-22得票数 1
1回答
在我的日常工作中，我经常处理包含数百万行的数据集，有时是上亿行，有时超过10亿行。这些数据集通常需要排序。键几乎总是大整数值(通常是9位数)。有时数据集具有9位和3位的组合键。
我想知道是否有可能在SAS中实现(LSD-first)基数排序宏，它可以用来代替PROC SORT来减少对这些数据集进行排序所花费的时间。我已经调整了排序，在适当的地方使用压缩，只保留相关的字段(或使用tagsort)，适当地调整字段长度，不进行不必要的排序等等。
我使用的硬件有局限性--让我们假设我只有2G的内存可供SAS使用，因此解决方案不需要将临时数组中的所有键值都放入内存中(至少不是一次全部放入)。
该解决方案
浏览 1提问于2011-12-23得票数 2
回答已采纳
我问这个问题是因为我很感兴趣，我想知道如何知道一个算法是否稳定。
稳定是什么意思？如果两个键相等的对象在排序输出中以相同的顺序出现，则排序算法是稳定的，就像它们出现在要排序的输入数组中一样。
如果我正确理解了算法，数组中的等量元素就不能分配给同一个数组，所以它是一个稳定的算法。
我怎么能让这个不稳定？我不想做很大的改变，那么将for i = n down to 1 do更改为for i = 1 to n do怎么样？我认为这应该是打破它的一种方式，但我不太确定。
Input: Array arr with n integers, from 1 to m
Output: Array arr so
浏览 2提问于2016-06-12得票数 0
2回答
我正在尝试用C语言使用POSIX线程来并行化基数排序。特殊之处在于需要为浮点数实现基数排序。目前，代码是按顺序运行的，但我不知道如何将代码并行化。有人能帮我吗？任何帮助都是非常感谢的。
浏览 6提问于2021-08-05得票数 0
既然所有比较排序算法至少需要n lg n时间，当我们可以将快速排序列表中的项表示为位并使用基数排序之类的线性排序时，为什么我们需要使用像快速排序这样的东西呢？
浏览 0提问于2014-10-01得票数 0
1回答
使用快速排序对长度为1到10^9 (= 10^6)的整数数组进行排序将得到O(n * log2 n)时间。但是如果我们应用基数排序，以n为基数，我们只需要传递4次。
我对基数排序复杂度的理解是O((n + b) * logb (k))，其中k是最大值，可以写成n^ c。O((n + b) * logb (n^ c) )取基数b等于n，O((n + n) *c)=O (2c * n)
快速排序是(n * log2 n)基数排序是(2c * n)
最大k(列表中的整数)是10^9，也就是n^c =k，因此c= 2。
当n=10^6时，log2 n等于20。
排序快速排序需要20n步，而基数排序需要
浏览 5提问于2019-12-17得票数 0
推力函数可以使用多个GPU进行计算吗？我已经写了这个推力代码，它在单个GPU上工作得很好。(特斯拉C2050)但我有另外三个特斯拉C2050卡连接到机器上，我想用它们来进行我的计算。
我知道，通过将多个GPU连接到一台机器上，我可以在每个GPU上并行运行一个CUDA内核，例如，在设备0上运行内核0，在设备1上运行内核1，等等。但在我的例子中，我想在一个单一的推力函数调用上使用所有4个GPU，比如推力：：排序。这个是可能的吗？
浏览 2提问于2012-02-04得票数 2
我听说基数排序的最坏内存情况是O(n+r)，其中n是数组大小，r是基数。但是，由于在计算中很少使用超过16进制的任何东西，那么在实践中，无论是r=2还是r=100真的很重要吗？对太空有什么真正的影响吗？
浏览 18提问于2020-09-23得票数 0
回答已采纳
我在一次面试中被问到了这个问题。我不能比O(NlogN)做得更好。我每次都在排序。
浏览 0提问于2018-05-23得票数 0
在c++语言中，为了获得O(n+m)的最佳时间复杂度，将两个未排序的数组排序到一个排序的数组中。我们如何修改这段代码，使其时间复杂度为O(m+n)？两个数组的大小应该不同。这里的时间复杂度为O((m+n)log(m+n))。如何使其复杂度达到O(m+n)？
#include <bits/stdc++.h>
using namespace std;
// Function to merge array in sorted order
void sortedMerge(int a[], int b[], int res[],
浏览 0提问于2020-06-24得票数 0
为了更好地理解算法，我正在尝试编写我自己版本的基排序。问题是，在第一个内部for循环(“j”)中，我得到了VS中的C6385错误。我不知道如何改写这一行，以使它发挥作用。我在这里做错什么了？
警告是：
警告C6385:从“countQueues”读取无效数据:可读的大小为'400‘字节，但可能读取'4000’字节。
void radixSort(int arr[], int arraySize)
{
int countDigits = GetMax(arr, arraySize); //max number of digits
queue<int&g
浏览 0提问于2020-03-19得票数 0
我知道32位整数被分解成8位的块。有人能给我解释一下通行证是如何工作的吗？一个简单的例子将帮助我更好地理解它。例如，我有2147507648和2147507672。我将它们分解为8位块。128093216是2147507672年度的分项数字，128093192是2147507648年度的分项数字。
我理解LSD基数排序是如何对基数10进行排序的。如果有人能在我得到8位块之后向我展示如何对这32位整数进行排序，我将不胜感激。
非常感谢!
浏览 2提问于2013-10-16得票数 0
假设我写了一个非常棒的接口。事实上，我想要一些我用来实现它们的内置类型，这样我写的任何使用这个接口的代码也可以使用内置类型。
public interface IKickAss
{
int Yeahhhhhhh() { get; }
}
public static class Woot
{
public int Bar(IKickAss a, IKickAss b)
{
return a.Yeahhhhhhh - b.Yeahhhhhhh;
}
}
// What I'd like to do, sort of.
public par
浏览 0提问于2009-04-29得票数 3
我实现了一个使用排序的算法。我尝试过Thrust::sort_by_key，对一个包含10^7个元素的数组进行排序大约需要0.4秒。
我认为bitonic排序网络应该比Thrust::sort_by_key更快。然而，bitonic排序需要大约2.5秒才能对上面提到的相同数组进行排序。我使用了SDK提供的bitonic排序网络。我只是稍微修改了一下原来的bitonic排序。
你能告诉我为什么吗？或者给我一些建议？
谢谢,
易克
2011年8月15日
浏览 2提问于2011-08-15得票数 1
回答已采纳
2回答
有没有办法使用GNU Coreutils排序与64位数字存储在二进制文件？如果文件不是二进制的，那么sort -n是解决方案，但我没有找到任何选项来使用它与二进制数据。
文件非常大(~100 to )，如果可能的话，我不想做它的文本(非二进制)拷贝。
数据示例：
$ xxd file 00292e0: 4036 1eb7 6888 d319 de6b 7402 9ca9 f116 @6..h....kt..... 00292f0: db68 7f05 199f 9d36 cf01 cb28 e49f 1116 .h.....6...(.... 0029300: 0c7c 8b55 2963
浏览 0提问于2014-09-26得票数 2
1回答
事情是这样的。我在做leetcode 164的最大间隔。这个问题的最佳解决方案是存储桶排序。
这让我对排序问题有了更多的思考。假设我们有一个列表，如下：
2 ,5 ,19,444，-14，89，16，77
我认为，我们可以将这些数字按两个不同的范围排列，( min，mid) ( mid，max)，而mid应该是min+ (max - min) / 2；
因此我们得到(-14,215) (216,444)
我们将min设置为最左边，max设置为最右边，并根据范围填充其他元素，然后我们得到
-14 2、5、19、89、16、77
444
我们回想一下两个范围的排序，对于左边的一个，我们有(-14，
浏览 5提问于2019-10-19得票数 0
2回答
我已经研究了基数排序算法的最佳、平均和最坏情况时间。
平均值为N×K/D
我知道K是钥匙/桶的数量
有人知道D代表什么吗？
参考-
浏览 4提问于2013-03-13得票数 0
3回答
基数是如何对浮点数据进行排序的？例如12.4，45.13等等，它会先读取小数点的右边吗?还是先读取小数点的左边?然后如果它读取小数点的右边，它将如何处理数字，它会先读取最右边的数字吗？
浏览 0提问于2011-01-16得票数 3
我在推力中使用sort和unique by key函数。我只是想知道在推力中排序函数的步长复杂度是多少，唯一的按键排序函数的功和步长复杂度是什么。
根据我的知识，我认为排序的工作复杂度是O(NlogN)。但是我不知道unique_by_key操作是什么
浏览 1提问于2012-04-03得票数 1
1回答
我正在尝试使用中的就地基数排序示例。到目前为止，我有这样的想法：
import std.random;
void swap(ref string i,ref string j) {
string tmp = i;
i = j;
j = tmp;
}
void radixSort(ref string[] seqs, size_t base = 0) {
if(seqs.length == 0)
return;
size_t TPos = seqs.length, APos = 0;
size_t i = 0;
while(i
浏览 0提问于2011-01-25得票数 6
回答已采纳
3回答
按所有元素对元组数组进行排序
、、、、
我想按所有元素对元组数组进行排序(就像它们在trie中一样)。如果输入是(1,2,5)，(1,2,3)，(1,1,4)，(2,8,9)，相应的输出将是(1,1,4)，(1,2,3)，(1,2,5)，(2,8,9)。相应的trie将是：
root
/ \
1 2
/ \ |
1 2 8
| /\ |
4 3 5 9
我在考虑对元组中的每个位置使用搜索树。还有一种明显的幼稚方式(按第一个位置排序，然后按第二个位置排序，等等)。有没有人看到更好的方法？
浏览 4提问于2013-03-19得票数 2
回答已采纳
2回答
我有一个包含uint32_t类型的结构数组。知道数组的最大值和最小值后，我想实现计数排序或基数排序，根据uint32_t对数组进行排序，值的范围可能会很大。我不知道如何对结构数组而不是整数数组进行排序。或者，有没有更好的排序算法？谢谢!
浏览 5提问于2015-05-09得票数 2
4回答
如果我有大量整数或浮点数，那么什么是排序的好算法/实现(在C中)？
在游戏里编辑有点晚了.但我在寻找正确性和速度。
浏览 2提问于2009-07-23得票数 2
回答已采纳
我正在阅读基数、计数和存储桶排序的定义，它们似乎都只是下面的代码：
public static void sort(int[] a, int maxVal){
int [] bucket=new int[maxVal+1];
for (int i=0; i<bucket.length; i++){
bucket[i]=0;
}
for (int i=0; i<a.length; i++){
bucket[a[i]]++;
}
int outPos=0;
for (int i=0; i<
浏览 2提问于2013-01-17得票数 59
回答已采纳
2回答
我有n个介于0和(n^4 - 1)之间的数字，最快的排序方法是什么？
当然，nlogn是微不足道的，但我考虑了基数n的基数排序选项，然后它将是线性时间，但我不确定，因为-1。
感谢您的帮助！
浏览 1提问于2015-09-01得票数 0
1回答
文件C#中的基数排序
、、、
我必须以两种方式对汽车牌照(ABC 123)进行基数排序: 1)数组2)链表。最有趣的是排序必须在文件中完成。例如，从现在开始，我们将只讨论数组。我生成车号并将其放入数组中，然后使用二进制写入将所有生成的汽车车牌写入该文件。之后，我将新生成的文件交给Radix Sort，他需要进行魔术操作。我将展示我目前的代码，但它实际上不是‘真正的’基数排序，因为我的大脑无法理解如何在文件中实现基数排序。(我已经实现了普通数组和链表的基数排序，但是当它在一个文件中完成时，它是令人兴奋的)。我只是想问你们是否有任何关于我如何改进排序算法的提示或想法，因为它非常慢。谢谢。
PROGRAM.CS
public s
浏览 5提问于2020-04-05得票数 2
1回答
对算法效率的很好的参考
、、、
我想通过自学从根本上学习算法效率(希望在程序如何最大限度地利用硬件和设计算法方面都是如此)。我想知道一些关于这个主题的好书。我用c编写我的程序。
浏览 0提问于2013-07-20得票数 3
回答已采纳
1回答
嗨，我正在尝试理解Radix排序的逻辑，我指的是维基百科的代码。这是接收数组的排序的排序函数，以及元素的数量。虽然代码运行得很好，但我不能理解代码的逻辑。在while循环中，我们首先初始化一个10位数的存储桶数组，该数组的第一个和第二个索引的计数分别为1和2。但在那之后，很难理解它试图做什么。
static void sort(int a[],int n)
{
int i=0;
int m =a[0];
int b[]=new int[n];
int exp=1;
for (i = 0; i < n; i++)
{
if (a[i] >
浏览 1提问于2012-11-30得票数 1
回答已采纳
1回答
好的，我必须为无符号整数和浮点数创建一个基数排序。我的无符号整数版本可以正常工作，但我在处理浮点值时遇到了一些问题。基本上，它按照浮点数的整数值对数组的值进行排序，但不会基于小数值对其进行排序。(例如36.65234将出现在36.02311之前，如果它出现在未排序的数组中)这段代码是我进行位操作和掩码的地方，我非常确定这就是我的问题所在。
/* For loop to create bin */
for(int i=0; i<n; i++){
temp_int = (((unsigned int)(list[i]))>>bitwise)&0xff;
b
浏览 0提问于2011-03-01得票数 5
回答已采纳
1回答
我一直在研究各种排序算法，有一种称为基数排序的算法，在这种算法中，我必须以2^(lg )为基数对数字进行排序，但我不知道这是什么。我的意思是，我知道基数2是二进制的，但是有了log n，我就不太明白了。
所以我想知道基数2^(lg )实际上是什么，以及它会以什么方式影响我的代码。
浏览 0提问于2020-05-07得票数 1
1回答
测量基数排序时的奇怪结果
、、、、
我正在使用timeit模块测量基数和计数排序的执行时间。我使用的是位于<0；1000000>区间上的100组随机整数。集合中的所有整数都是唯一的。第一组由10000个整数组成，最后一组包含1000000个整数。每组排序10次，记录平均时间(作为full time/10)。在基排序的日志文件中有一些奇怪的结果，我不确定这是timeit模块的问题还是我的排序算法的问题：
基排序日志
integers count, average time
......,.............
760000,1.51444417528
770000,1.31519716697
780000,1.33
浏览 2提问于2014-12-28得票数 0
1回答
O(n)中的2键搜索算法
、、、
我必须找到一个算法来对一个复杂度为O(n)的数组进行排序。该数组的长度为n，具有两个不同的键。
例如，java中的数组：
int[][] array = {{1,2},{2,1},{1,1}};
结果应该是
1 1
1 2
2 1
我在努力解决这个问题..
谁能帮我呢？
提前感谢
浏览 2提问于2013-03-19得票数 0
回答已采纳
1回答
我试图用O(1)空间实现一个稳定的基排序。我看过Wikipedia，我注意到C实现使用一个临时变量来保存每次传递的排序值，而“就地”MSD基排序实现的部分非常混乱。
我使用了C代码，并尝试在C++中实现它，以获得稳定的本地基排序版本：
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
void radix_sort(vector<int>& v) {
//search for maximum number
int
浏览 0提问于2013-03-17得票数 6
回答已采纳
1回答
使用JAVA，我尝试按基数排序对整数(升序)进行排序和数组，但似乎解决不了这个错误。
public class Ex_radix {
public static void radixSort(int[] A) {
int d = 0;
for (int digit = 0; digit < A.length; digit++) {// Checks what is the
// maximum amount of
浏览 1提问于2013-12-02得票数 0
我有一个带有许多集合的Redis数据库，所有集合都由一个共同的键模式标识，比如"myset:“。
有没有一种方法，从命令行客户端，按包含的元素数量对所有集合进行排序，并返回该信息？据我所知，SORT命令只接受单键。
我知道使用编程语言可以很容易地做到这一点，但我更喜欢不需要在服务器上安装任何驱动程序、编程环境等的情况下就能做到这一点。
谢谢你的帮助。
浏览 3提问于2012-09-10得票数 4
回答已采纳
2回答
我有一个给定的日期字符串数组，格式是dd/mm/yyyy。
我想用基数排序按月和年排序，但我不知道如何排序，因为最终它将根据月份的最大数目进行排序。
例如，我有以下数组: 16/04/2012 01/05/2013 01/02/2012 10/11/2012 01/12/2012
通常排序后的结果是: 01/02/2012 16/04/2012 01/05/2013 10/11/2012 01/12/2012
而我想要的是: 01/02/2012 16/04/2012 10/11/2012 01/12/2012 01/05/2013
我还没有编写代码，因为我不知道算法是如何工作的，我只能用生成
浏览 11提问于2012-05-02得票数 0
回答已采纳
2回答
假设我有一个数字列表，并且对于每个数字n，我知道n是由一些恒定的位数表示的。
即使我的数字是实数而不一定是整数，我也可以使用基数排序吗？
浏览 0提问于2016-04-07得票数 1
2回答
理解C中的基类
、、、
我正在使用这个作为参考，看看算法是如何实现的。除本部分外，我大部分理解：
/*
* update all the buckets. If bucket[8] has 2,
* then there are 2 elements present till bucket 8
*/
for (i = 1; i < 10; i++)
bucket[i] = bucket[i] + bucket[i-1];
我不明白作者在那个循环中做了什么。有人能解释一下发生了什么事吗？
是的，我正在用纸和笔来观察到底发生了什么。我只是想澄清一下
浏览 2提问于2013-09-18得票数 0
回答已采纳
2回答
我正在复习DC3算法，这是一种用于构造后缀数组的线性时间算法。我无法理解论文中的一种技术，它可以是。
我不能理解论文第6页提到的重命名是如何完成的。如何按照步骤1进行重命名。附录中的相关代码部分如下：
for (int i = 0; i < n02; i++)
{
if (T[SA12[i]] != c0 || T[SA12[i]+1] != c1 || T[SA12[i]+2] != c2)
{
name++; c0 = T[SA12[i]]; c1 = T[SA12[i]+1]; c2 = T[SA12[i]+2];
}
浏览 6提问于2013-09-04得票数 2
与基于比较的排序算法相比，我是关于基数排序效率的，在这里我发现了以下内容：
例如，考虑自下而上的合并排序。第一次传递将比较随机键对，但最后一次传递将比较排序顺序非常接近的键。这使得合并排序在这类输入上花费了O(n (log )2)时间。
有人能帮我理解O(n (log n)2)部分吗？
浏览 4提问于2016-03-13得票数 0
回答已采纳
5回答
任意长度字符串的基数排序
、、、
我需要对任意长度的大量文本字符串进行排序。我想基数排序是这里最好的选择。List真的很大，所以填充相同长度的字符串是完全不可能的。
对于这个任务，有没有现成的实现，最好是用C#？
浏览 0提问于2010-09-10得票数 1
你有一个数组和一个目标。查找数组中两个元素的差异。这种差异应该离目标最近。
(即，查找i, j，使(array[i]- array[j])最接近目标)
尝试：I使用order_map (C++哈希表)存储数组的每个元素。这将是O(n)。然后，我将有序元素输出到一个新的数组中(这个数组是排序增加的)。
接下来，我使用两个指针。
int mini = INT_MAX, a, b;
for (int i=0, j = ordered_array.size() -1 ; i <j;) {
int tmp = ordered_array[i] - ordered_array[j];
浏览 5提问于2017-07-26得票数 0
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
腾讯会议
实时音视频活动推荐
腾讯云开发者
