2回答
正如问题所述，我想确认计数排序算法是否是就地排序算法。
维基百科将描述为
在计算机科学中，就地算法(或拉丁文原位算法)是一种使用数据结构转换输入的算法，该算法具有较小的、恒定的额外存储空间。当算法执行时，输入通常被输出覆盖。一种不到位的算法有时被称为“不到位”或“异地”(或拉丁文中的“异地”)。
稳定的排序算法用等键(即值)保持记录的相对顺序。也就是说，排序算法是稳定的，如果有两个记录R和S具有相同的键，而R出现在原始列表中的S前面，则R将出现在排序列表中的S之前。
也在计数排序页面下面的某个地方：
如前所述，计数排序不是一种就地算法；即使不考虑计数数组，它也需要单独的输入和输出数组
浏览 3提问于2015-05-13得票数 5
回答已采纳
1回答
我必须排序一个表(向量)，这个表的大小是n，在这个表中有从0到n-1的不同的数字。是否有可能对此表进行排序(使用另一个表，而不使用新表)？这类的复杂性应该在O(n)中。
浏览 0提问于2018-10-13得票数 0
6回答
上周，我无意中发现了，作者在第二页中提到了这一点：
请注意，这将产生整数边权值的线性运行时间。
在第三页上也是如此：
这就产生了整数边权值的线性运行时间和基于比较排序的O(m log n)。
在第8页：
特别是，使用快速整数排序可能会大大加快GPA。
这是否意味着在特殊情况下存在整数值的O(n)排序算法？还是这是图论的专长？
PS:
可能是参考3可能有帮助，因为他们在第一页上说：
已经取得了进一步的改进。图类，如整数边权值3，
但我没有机会接触任何科学期刊。
浏览 14提问于2010-02-28得票数 62
回答已采纳
1回答
我正在进行一个改进快速排序算法、最坏情况时间复杂度的项目。我修改了算法，选择中间枢轴而不是最左边的选择，并在一定次数的迭代后引入插入排序。结果如下：
对于长度为5000至100000的未排序数据的输入：
在我的修改后的快速排序中进行的比较比在常规的快速排序中进行的比较的数量要少得多。
对于所有长度的if数据，两者的运行时间为零秒。
对于长度为5000至100000的已排序数据的输入：
修改后的快速排序中进行的比较数量仍然比在常规快速排序中进行的比较数量少得多。
修改后的快速排序所用的时间比对所有长度的数据进行常规快速排序所需的时间要短得多。
现在我如何证明已经排
浏览 3提问于2011-12-03得票数 1
2回答
这类存在吗？
、、
我已经阅读了一些关于算法的旧书，并学习了不同类型的算法。看起来所有最快的排序算法都是在O(nLogn)时间内运行的，它让我思考为什么这是我们所能做的最好的？我编写了另一个算法，它在某些情况下运行得更好(除非我遗漏了什么)，但在其他情况下却非常糟糕。这是一种正在使用的算法吗?我只是在这里重新发明方向盘？
public class Main {
public static void main(String[] args) {
// array sort looks like it performs best in this example.
// this is because
浏览 2提问于2014-12-29得票数 1
回答已采纳
我试图了解非基于比较的排序算法与基于比较的排序算法的主要缺点。
这主要是因为非基于比较的排序算法在非固定长度输入方面做得不好吗？
假设我有4个元素1,100000000000000000000024，3，5
一种基于比较的排序算法将在4* log(4)中求解。
而非基于比较的排序算法将在4*length_of(“1000000000000000000024”)中求解，前提是我们使用键0到9，并使用诸如LSD或MSD之类的算法。
或者假设我们知道数字介于0到10000000000000000000000024之间，我们可以有从0到1000000000000024之间的键，但这是非常低效率的，因为
浏览 3提问于2013-09-15得票数 0
回答已采纳
1回答
以下可数排序的实现有多复杂？
void countSort(vector<int>& input)
{
map<int, int> freq;
for (int x: input) {
freq[x]++;
}
int i = 0;
for (auto p: freq)
{
while (p.second--) {
input[i++] = p.first;
}
}
}
有人告诉我是O(n)。这不是for吗
for (int x: in
浏览 3提问于2022-01-10得票数 0
如何使用计数排序两次对数组中的元素进行排序？ 是否修复了使用计数排序两次的问题？ 我知道它与基数排序(这是计数排序的子例程)有关，在基数排序中，元素是通过一次考虑每个数字来排序的。 有关更多详细信息，请访问- https://www.geeksforgeeks.org/sort-n-numbers-range-0-n2-1-linear-time/ (请不要声明为重复，我已经检查了与此相关的帖子。) 在将数字转换为基数n之后，元素将如何成为两位数？你能告诉我这个吗？ 提前谢谢。
浏览 36提问于2021-05-04得票数 0
1回答
其思想是在最终数组中将所有值设置为其父索引，然后删除所有空值。下面是一些简单的实现：
int x[] = {9,3,4,2,1,12,5};
sortList(x)
public static int[] sortList(int[] x){
int[] y = new int[15];
for (int i=0; i < x.length; i++){
int value = x[i];
y[value] = value;
}
return removeNull(y);
}
public static int[] rem
浏览 1提问于2017-12-22得票数 0
1回答
当我读到一本关于“算法分析”的书时，我偶然发现了count_sort算法。然而，我在其他地方读到过“快速排序/合并排序”是最好和最有效的排序算法。我觉得这很让人困惑，因为count_sort的复杂性是O(n+k)，这比Mergesort和Quicksort ( O( n ) )要好。
我的问题是：
这个排序算法有什么问题？
什么是最好的排序算法？def count_sort(seq)：b，c= []，defaultdict(list)表示在seq中的x: cX.append(x)表示k在范围内(min(C)，max(c)+1)：b.extend(cK)返回b
浏览 0提问于2014-09-02得票数 0
我有一个包含一个循环的图，但是我需要使用“拓扑排序”(当然，实际的拓扑排序不处理循环)对它进行排序。我在想怎么做呢？
例如：
A -> B
B -> C
C -> D
D -> A
可能的解决办法是：
A -> B -> C -> D
B -> C -> D -> A
C -> D -> A -> B
D -> A -> B -> C
我看到了作为，但是它对我的用例来说太复杂了。
浏览 5提问于2022-06-23得票数 0
回答已采纳
假设我有一个n个整数的数组，我需要创建一个数据结构，它可以让我找到数组中某个范围a，b中的整数的数量。
浏览 1提问于2010-11-07得票数 0
我在互联网上到处找过，找不到这样的wc时间复杂度排序算法.
我相信这不是Bogo ，因为wc不是无穷大的
浏览 2提问于2020-12-09得票数 1
C#的List<T>.Sort()的时间复杂度是什么
我猜是o(N)
但在我搜索了很多次之后，我没有得到任何准确的结果。
浏览 7提问于2012-03-08得票数 17
回答已采纳
考虑示例输入数组= 7,5,0,1，排序输出数组= 0,1,5,7。从本例中可以看出，没有循环。如果我对这样的输入应用循环排序，速度会有什么不同吗？循环排序的工作原理是旋转循环以生成排序后的输出。在没有循环的输入中，使用循环排序有什么好处？
浏览 0提问于2017-05-08得票数 0
2回答
下面的陈述是正确的还是错误的？
使用预置的通用算法永远不会有比O(nlogn)更糟糕的效率。
我想这是真的。因为这个的大O是O(nlogn)
浏览 5提问于2017-03-01得票数 0
1回答
我需要帮助理解编程挑战
、、、
我正试着做一些家庭作业，不能把我的头绕在一个问题上。我已经张贴在课堂讨论板和电子邮件教授，但没有得到任何帮助。
问题是:设计一个类abstractSort，用于分析排序算法执行的比较数。类应该具有能够比较两个数组元素的成员函数比较，以及跟踪执行的比较数量的方法。该类应该是一个具有纯虚拟成员函数的抽象类。
virtual void Sort(int arr[], int size)= 0;
当重写时，它将通过调用函数来对数组进行排序，以确定数字对的相对顺序，(这是我不理解的短语)。创建一个AbstractSort的子类，它使用简单的排序算法来实现排序函数。类应该有一个成员函数，可以在排序之后调用
浏览 0提问于2015-03-08得票数 3
回答已采纳
4回答
for(int i=0; i<n-1; i++)
{
for(int j=i+1; j<n; j++)
{
if(a[i] > a[j])
{
/* Swap a[i] and a[j] */
}
}
}
P.S.给出了一个算法的名称，可以很容易地找到相关的源代码。但我发现很难做到反之亦然:D
编辑哦！如果这是气泡排序，那么它的名称是什么：
for(int i=0; i<n; i++)
{
for(int j=0; j<n-1; j++)
{
浏览 2提问于2011-03-18得票数 6
回答已采纳
3回答
对二值列表进行排序
、、、
如果我有一个只包含0和1的二进制值的列表，比如下面的000111010110，我想把它排序到下面的000000111111，如果你也知道列表的大小，那么最有效的方法是什么？现在，我正在考虑有一个计数器，当我从头到尾遍历列表时，我只计算0的数量。如果我把listSize除以numberOfZeros，就会得到numberOfOnes。然后我在想，与其从零开始重新排序列表，不如创建一个新的列表。你同意这是最有效的方法吗？
浏览 1提问于2012-10-27得票数 1
回答已采纳
我正在尝试的算法是，你可以根据用户看到项目的次数和速度对项目进行排序。它在许多网站(按相关性分类)中都有Stack Overflow，并且使用非常广泛。我正在尝试的算法只是用户看到链接的速度和他们看到链接的次数的组合。
浏览 2提问于2013-04-15得票数 0
回答已采纳
我需要在一个包含多达500,000个元素的列表中使用排序算法。该程序在嵌入式PC上运行。有人知道哪种排序算法在时间复杂度和内存方面都有最好的性能吗？
浏览 2提问于2011-06-27得票数 0
回答已采纳
3回答
长话短说，我想出了这个算法，但我怀疑我是不是发明了什么。那么这个叫什么呢？ 我知道它在多个领域有很多限制。例如，此实现不能对高于UInt16的数字进行排序，并且限制为最多出现int.MaxValue次。我也可能在某个地方遇到一些数组边界问题。它已经像吃蛋糕一样吃掉了RAM :) 实际算法是在CustomSort方法中实现的。其余的是我用来测试的代码。 class Program
{
static Random r = new Random((int)DateTime.Now.Ticks);
static int[] GetRandomIntege
浏览 32提问于2020-04-07得票数 3
回答已采纳
嘿，我正在努力学习DS&A，我试着理解这个问题，但我不明白。我看过其他表格，但大多数都是用其他语言写的。有人能用最简单的JAVA形式向我解释一下这个问题吗？谢谢
浏览 3提问于2022-09-28得票数 -2
如果我有一个大小为n的列表，并且我知道列表中的数字将介于1到2n之间，我将如何解决最坏情况是O(n)的问题呢？
我在想，如果它介于1和n之间，我只需要取这个数字，并将它与数组的值交换-1，但是如果有任何重复的话，它就不会排序。
我在考虑一种类似的方法，对于数字介于1到2n之间的列表，但我似乎无法弄清楚。有什么帮助吗？
浏览 6提问于2013-12-01得票数 5
回答已采纳
1回答
我正在一个处理数据的程序中工作。但是，由于我希望我的代码高效，我想要一个排序算法，它的运行时间不取决于数组的反转次数，所以我可以按升序排序。数组的顺序总是：
N=阵列大小
list = (1,2,3，…，(n/2-1)，(n/2)，(n/2 + 1)，...3,2,1
我知道数组的反转总数等于：
(n/2-1)+(n/2-2)+(n/2-3) +...+ 1
我认为对于一个对称数组来说，这是一个很大的反转，因为我知道数组的顺序总是这样的，所以我想要一个算法来对它们进行O(n)时间排序。我知道插入排序的复杂性取决于数组的反转次数，但我不确定依赖于n的数组反转的数量是多
浏览 4提问于2017-03-22得票数 0
5回答
我在一些大型学术文件中打印字母频率。作为这一过程的一部分，is将这些文档的大剪报中的字母按字母顺序排序。我正在使用内置于Python's中的排序的函数，我开始怀疑是否可以使它更快。然后我编写了以下函数：
def count_sort(l):
items = {'a':0,'b':0,'c':0,'d':0,'e':0,'f':0,'g':0,'h':0,'i':0,'j':0,'k':0,&#
浏览 7提问于2015-05-08得票数 2
回答已采纳
2回答
在8086中，如何有效地对3字节无符号数字进行排序？
当前解决方案：
比较上16位
如果它们相等，则比较低的8位。
根据结果交换
浏览 1提问于2014-11-16得票数 0
回答已采纳
我只是做了一个数组问题，那里的解决方案使用了快速排序，但是我使用了Arrays.sort() method.Now，我认为Arrays.sort()使用了带基本类型的快速排序，对于对象类型使用了mergesort。那么，使用
Arrays.sort()
方法直接在java中执行，而不是为Quick sort.Or执行整个实现，如果两者相同，为什么不使用Arrays.sort()方法执行冗长的实现？
浏览 0提问于2016-04-17得票数 1
回答已采纳
考虑两个k位数(以二进制表示)：
$$A = A_1 A_2 A_3 A_4 ... A_k $$
$$B = B_1 B_2 B_3 B_4 ... B_k $$
为了进行比较，我们从左到右扫描，查找0的出现，如果该数字也是0 (对于两个数字)，则检查相反的数字，注意如果发现这样的情况，则0的源小于1的源。但是如果数字是：
111111111111
111111111110
显然，这将需要扫描整个数字，如果我们事先没有被告知任何关于数字的信息，然后简单地给出它们：
比较需要$O(k)$时间。
因此，当我们查看排序方法的代码时，例如高性能的快速排序：
HPQuicksort(list): T
浏览 0提问于2014-02-14得票数 1
4回答
请提及时间复杂度和存储这些值的最佳数据结构，当值为：
整数
字符串(字典，如排序)
我知道当整数在一个小范围内时，是首选的。
谢谢。
编辑:对不起，我问了一个不同的问题。实际的问题是，如果整数是电话号码(字符串是名称)，然后找到最佳排序算法，那么什么才是存储这些值的最佳数据结构。
浏览 2提问于2010-08-23得票数 1
回答已采纳
8回答
根据题目，如果数组的长度为奇数，并且数组元素的编号为1- 10。
例如，
3 6 8 1 3 7 7 9 4 1
我在考虑使用堆排序？由于它是一个数组，合并排序和插入排序需要移位，因此效率不高。
浏览 108提问于2011-09-29得票数 21
回答已采纳
2回答
给定一个整数数组，在最坏的情况下，时间复杂度是多少？
我认为这可以在O(n)中通过使用计数、排序或异或来实现。我说得对吗？
问题并不担心空间的复杂性和答案，O(Nlgn)说.
浏览 1提问于2016-08-30得票数 0
回答已采纳
不相交集问题
设A和B是两组，它们不相交吗？
问题
证明了求解不相交集的任何算法至少需要O(nlog n)。
我想到的想法是证明排序可以简化为不相交的集合问题。
我该怎么做？
浏览 3提问于2015-02-12得票数 0
回答已采纳
如果有n个变量，每个变量都有m个可能的值。(对于整数，m是20亿左右。)
首先，按顺序将每个可能的值映射为从0到m-1的整数.并定义映射函数。
index(v): value to integer
value(i): integer to value
其次，循环n个变量并计算每个值出现的次数。
for v in variables {
counter[index(v)] += 1
}
最后，循环计数器数组并将值放入结果数组。
for i in 0...m-1 {
for j in 1...counter[i] {
result.append(value(i))
浏览 0提问于2018-12-19得票数 3
我已经按桶排序为数字数组创建了一个程序。为此，我按照bin sort方法创建了一个链表数组。
// Bucket or Bin sort
#include<iostream>
using namespace std;
//Bin sort has linear complexity( O(n))
// node class
class node
{
public:
int data;
node *next;
};
// print array function
void
print (int arr[], int n)
{
for (int i = 0; i &
浏览 5提问于2022-11-23得票数 0
1回答
如果有一组节点N和一组顶点V_1定义具有一定拓扑顺序的图G_1，那么如何检查来自N的节点子集和定义图G_2的新顶点V_2是否保持G_1的拓扑顺序？
例如：
G_1:
D -> E
B -> C
A -> C
G_1：[A, B, C, D, E]的拓扑序
G_2:
D -> B
B -> E
G_2：[D, B, E]的拓扑序
我在考虑某种蛮力方法，生成G_1的所有拓扑顺序，从这些命令中删除在G_2中找不到的节点，并检查是否有任何与G_2的第一个排序相匹配的方法。
我的潜在解决方案正确吗？你有更好的建议吗？
浏览 1提问于2018-07-27得票数 1
回答已采纳
我在一次面试中被问到了这个问题。我不能比O(NlogN)做得更好。我每次都在排序。
浏览 0提问于2018-05-23得票数 0
2回答
我在使用计数排序按字母顺序对名称进行排序时遇到了困难，例如，我应该按字母顺序排序，并将数字输入添加到其中，例如0001 Alex Smith, Gregory John, Alex Smith, Adam Richard, Alex Ryan。输出应按以下顺序进行：
亚当·理查德
亚历克斯·瑞安
亚历克斯·史密斯
格雷戈里·约翰
到目前为止我的代码是：
public class Names
{
//private static int[] c;
public ArrayList<String> getUserInput()
{
ArrayList<
浏览 1提问于2011-09-27得票数 0
我可以对一个巨大的数字池中的一个小范围的数字进行计数排序吗，比如A=7,9,12,15，我知道这将只由小数组中的数字组成？或者小范围总是必须是0..k。
我可以通过说0..15对数组A进行计数排序，但这没有意义。如果A=100,750,452
所以我想这是可行的。我想要一些投入，请。
浏览 1提问于2011-03-22得票数 0
4回答
这里有一个脑筋急转弯，已经在我的脑海中停留了几天。
我们有一个包含n个元素的序列S。每个元素都是0，n^2-1范围内的整数。描述一种在O(n)时间内对S进行排序的简单方法。
我可能遗漏了一些显而易见的东西，但如果有任何见解，我会很感激。
浏览 1提问于2010-10-11得票数 3
回答已采纳
1回答
我想用TBB“模拟”mapreduce进行软件分配，因为串行过滤器可以是I/O，并行过滤器可以是Map和Reduce实现，但是这个函数实现可以接收和返回单个元素(如果输入只生成一个元组，那么像单词计数这样的东西需要多个输出，那么简单地减少全局hashmap上的聚合而不返回“东西”如何？)
是否有为此目的使用管道的方法，或者我应该使用类似并行_while/ for之类的方法？
谢谢!
浏览 1提问于2014-05-09得票数 1
回答已采纳
2回答
何时使用排序而不是其他排序
、、、、
在Quicksort、MergeSort和Binary Insertion Sort中，有没有出现过使用其中任何一个而不是另一个的情况？
我知道像快速排序这样的东西在几乎排序的列表上可能会出现问题(但我相信旋转的随机分配可以消除最坏的情况下的时间)，所以使用MergeSort可能更好。MergeSort可能比QuickSort使用更多的空间，我不完全确定，Merge可能对LinkedLists更好。
我猜二进制插入排序更适合较小的列表？如果是这样的话，是否有使用这个的门槛，或者大小只是留给解释？例如，如果列表大小为3，我们是否应该使用二进制插入排序而不是Quick或Merge？
浏览 0提问于2011-04-26得票数 1
5回答
我是学习算法的新手--我也不是计算机科学专业的毕业生。
然而，在阅读线性排序非比较算法时，我可以理解基数排序是计数排序的扩展。
我不清楚的是计数排序的限制。
当计数排序似乎可以避免O(n*logn)比较时，我为什么要使用基数排序呢？
当然，它看起来确实是一个更简单的实现。
浏览 2提问于2013-07-15得票数 3
回答已采纳
2回答
如何找到数组中的倒数个数？
、、、、
基本上，我正在尝试用Java编写一个算法来确定数组中乱序的对的数量。所以如果我们取i和j，并且j在数组中的位置比i更高，但是Ai > Aj，那么它把这两个数算作反转。目前，我所拥有的是：
for(int i = 0; i<n-1; i++){
if (A[i] > A[i+1]){
k++;
我知道如何做这样的事情，但我希望运行时是(n+k)，其中n是数组的长度，k是数组中的反转次数。
编辑:这是我实现插入排序的尝试：
int k = 0;
int [] A = {5, 4, 3, 2, 1};
int n = A.length;
for(int i
浏览 0提问于2015-10-14得票数 2
2回答
我正在阅读，但我不明白:为什么这与简单的排序问题不同？
我的意思是:如果我们将0指定为红色，1为白色，2为蓝色，然后进行标准的快速排序或其他任何操作。为什么我不能得到正确的答案？
我是不是遗漏了什么？
浏览 5提问于2015-07-04得票数 2
回答已采纳
我在Python中为问题找到了一个解决方案，它使用“非比较排序算法来获取计数”。它对执行按位操作的代码进行2次递归调用。
def inv_count(a, m=(1 << 32)):
if not m or not a:
return 0
count = 0
ones, zeros = [], []
for n in a:
if n & m:
ones.append(n & ~m)
else:
count += len(ones)
浏览 6提问于2015-07-19得票数 2
回答已采纳
1回答
我的程序应该运行一个循环，用随机值填充数组，然后使用选择排序、增强气泡排序和插入排序对数组进行排序。问题是，它每次都返回相同的比较计数。
为什么我的代码总是返回相同的比较计数？
import java.util.Random;
public class AssignmentIV {
public static void main(String[] args) {
int[] testRuns = new int[4]; //stores the values for the generation of random arrays
testRuns[0] = 1
浏览 0提问于2018-04-28得票数 1
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
实时音视频
对象存储
即时通信 IM活动推荐
腾讯云开发者
