天道酬勤,学无止境

计数排序 C++11(Counting Sort C++11)

问题

这是在 c++11 中计数排序的实现。 它不提供任何输出。 可能出了什么问题? std::copy 不应该将排序后的数组复制回原始数组吗?

void counting_sort::sort_array(int array[], int n)
{
std::vector <int> a;
a.insert(a.end(), &array[0], &array[n]);
std::vector <int> b;

auto k = *std::max_element(a.begin(), a.end());
auto m = *std::min_element(a.begin(), a.end());

auto x = k - m + 1;
std::vector<int>v(x);

    for(int i = 0; i < a.size(); i++)
        v[a[i]-m]++;

    for(int i = 1; i < v.size(); i++)
        v[i]=v[i]+v[i-1];

    for(int i = a.size()-1; i >= 0; i--)
        { 
        b[v[a[i]-m]-1] = a[i]; 
        v[a[i]-m]--; 
    }

std::copy(b.begin(), b.end(), array);

}

标签

受限制的 HTML

  • 允许的HTML标签:<a href hreflang> <em> <strong> <cite> <blockquote cite> <code> <ul type> <ol start type> <li> <dl> <dt> <dd> <h2 id> <h3 id> <h4 id> <h5 id> <h6 id>
  • 自动断行和分段。
  • 网页和电子邮件地址自动转换为链接。

相关推荐
  • 基数排序 vs 计数排序 vs 桶排序。 有什么不同?(Radix sort vs Counting sort vs Bucket sort. What's the difference?)
    问题 我正在阅读基数、计数和桶排序的定义,似乎所有这些都只是下面的代码: 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<bucket.length; i++){ for (int j=0; j<bucket[i]; j++){ a[outPos++]=i; } } } 我知道我不可能是对的,所以我错过了什么? 如果您认为这有助于用 Java 或 C 进行解释,请展示代码。 回答1 让我们从用 C 重写您的代码开始,因为我更熟悉 C 来解释。 所以让我们用一些注释来回忆你的代码: int counting_sort(int a[], int a_len, int maxVal) { int i, j, outPos = 0; int bucket_len = maxVal+1; int bucket[bucket_len]; /* simple bucket structure */ memset(bucket
  • 如何在现代C ++中实现经典的排序算法?(How to implement classic sorting algorithms in modern C++?)
    问题 在大多数实现中,C ++标准库中的std::sort算法(及其表亲std::partial_sort和std::nth_element )是更多基本排序算法(例如选择排序,插入排序,快速排序)的复杂混合混合,合并排序或堆排序。 在这里以及在姐妹网站(例如https://codereview.stackexchange.com/)上,存在许多与这些经典排序算法的错误,复杂性以及实现的其他方面有关的问题。 提供的大多数实现都是由原始循环,使用索引操作和具体类型组成的,并且在正确性和效率方面进行分析通常并不简单。 问题:如何使用现代C ++实现上述经典排序算法? 没有原始循环,但结合了<algorithm>标准库的算法构造块迭代器接口和模板的使用,而不是索引操作和具体类型的使用 C ++ 14样式,包括完整的标准库以及语法降噪器,例如auto ,模板别名,透明比较器和多态lambda。 注意事项: 有关排序算法实现的更多参考,请参见Wikipedia,Rosetta Code或http://www.sorting-algorithms.com/ 根据Sean Parent的约定(幻灯片39),原始循环是for循环的时间,长于带有操作符的两个函数的组合。 因此f(g(x)); 或f(x); g(x); f(x); g(x); 或f(x) + g(x); 不是原始循环
  • 关于计数排序算法(about counting sort algorithm)
    问题 我已经阅读了一种计数排序算法,如下所示: Counting Sort(A[1,..n]) //C[1,...k] is the temporary memory and k is the range of integers for i<-- 1 to k C[i]<-- 0 for j<-- 1 to n C[A[j]]<--C[A[j]]+1 for i<--2 to k C[i]<--C[i]+C[i-1] for j<--n downto 1 B[C[A[j]]]<--A[j] C[A[j]]<--C[A[j]]-1 我想知道,如果我将最后一个更改为: for j<--1 to n ,该算法也将是正确的? ???) 也这样算法稳定吗? 谢谢 回答1 这两种算法都是正确的。 正如您现在拥有的那样,它也很稳定。 如果将最后一个更改for您所说的内容,它将停止保持稳定。 基本上, C[i] = how many elements <= i exist在第三个for循环结束后C[i] = how many elements <= i exist 。 因此, C[A[j]]会按排序顺序为您提供值A[j]的元素的最后位置, C[A[j]] - 1为您提供值A[j]的元素的最后第二个位置,以及很快。 这就是为什么要递减C的值。 因此,如果您关心稳定性
  • 13.线性排序
    目录 1 线性排序算法介绍 2 桶排序(Bucket sort) 2.1算法原理: 2.2使用条件 2.3适用场景 2.4应用案例 3 计数排序(Counting sort) 3.1算法原理 3.2代码实现(参见下一条留言) 3.3使用条件 4 基数排序(Radix sort) 4.1算法原理(以排序10万个手机号为例来说明) 4.2使用条件 5 思考 1 线性排序算法介绍 1.线性排序算法包括桶排序、计数排序、基数排序。 2.线性排序算法的时间复杂度为O(n)。 3.此3种排序算法都不涉及元素之间的比较操作,是非基于比较的排序算法。 4.对排序数据的要求很苛刻,重点掌握此3种排序算法的适用场景。 2 桶排序(Bucket sort) 2.1算法原理: 1)将要排序的数据分到几个有序的桶里,每个桶里的数据再单独进行快速排序。 2)桶内排完序之后,再把每个桶里的数据按照顺序依次取出,组成的序列就是有序的了。 2.2使用条件 1)要排序的数据需要很容易就能划分成m个桶,并且桶与桶之间有着天然的大小顺序。 2)数据在各个桶之间分布是均匀的。 2.3适用场景 1)桶排序比较适合用在外部排序中。 2)外部排序就是数据存储在外部磁盘且数据量大,但内存有限无法将整个数据全部加载到内存中。 2.4应用案例 1)需求描述: 有10GB的订单数据,需按订单金额(假设金额都是正整数)进行排序 但内存有限
  • Counting the number of elements with the values of x in a vector(Counting the number of elements with the values of x in a vector)
    问题 我有一个数字向量: numbers <- c(4,23,4,23,5,43,54,56,657,67,67,435, 453,435,324,34,456,56,567,65,34,435) 我如何让R计算向量中出现值x的次数? 回答1 You can just use table(): > a <- table(numbers) > a numbers 4 5 23 34 43 54 56 65 67 324 435 453 456 567 657 2 1 2 2 1 1 2 1 2 1 3 1 1 1 1 Then you can subset it: > a[names(a)==435] 435 3 Or convert it into a data.frame if you're more comfortable working with that: > as.data.frame(table(numbers)) numbers Freq 1 4 2 2 5 1 3 23 2 4 34 2 ... 回答2 最直接的方法是sum(numbers == x) 。 numbers == x创建一个逻辑向量,该逻辑向量在x出现的每个位置均为TRUE,并且sum ,该逻辑向量被强制转换为数字,从而将TRUE转换为1,将FALSE转换为0。 但是,请注意,对于浮点数
  • Python-排序-有哪些时间复杂度为O(n)的排序算法?
    人到中年,容易变得油腻,思想懒惰,身体就容易发胖。为了摆脱中年油腻,不如和我一起学习算法来烧烧脑子,燃烧你的卡路里。烧脑题目:如何在 O(n) 的时间复杂度内按年龄给 100 万用户信息排序?带着这个问题来学习下三个线性排序算法。前几篇文章介绍了几个常用的排序算法:冒泡、选择、插入、归并、快速,他们的时间复杂度从 O(n^2) 到 O(nlogn),其实还有时间复杂度为 O(n) 的排序算法,他们分别是桶排序,计数排序,基数排序,因为这些排序算法的时间复杂度是线性的,所以这类算法也叫线性排序。你可能会问为什么这些时间复杂度低至 O(n) 的排序算法会很少使用呢? 那就是因为这些排序算法对待排序的数据要求比较苛刻,这些算法理解其来比较简单,学习这类算法重要的是掌握它们的适用场景。下面我给出每一种算法的实现思路,Python程序实现和应用场景。1、桶排序桶排序,可以这样去理解:想像你面前有 m 个桶,有一堆待排序的 n 个数据,可以将这 n 个数据先按次序划分成 m 个区间,对应依次放入这 m 个桶里,然后对每个桶内的数据进行排序,再依次从 1 到 m 个桶里依次取出就得到有序的结果。换成这样描述会更容易理解。假如要对 100 个订单的金额进行排序,订单的金额都是整数,订单金额从 1 到 100 不等,那么可以将这 100 个订单分成 10 个区间,放到 10 个桶中,1 至 10
  • 当整数来自范围 [1,100] 时,对 100 万个整数进行排序的最快方法是什么?(What is the fastest way to sort 1 million integers when integers are from the range [1,100]?)
    问题 笔记:我考虑过基数排序、桶排序、计数排序。 有没有办法实现大O(n)? 回答1 您可以使用计数排序。 计数排序(有时称为超排序或数学排序)是一种排序算法,它(如桶排序)利用知道要排序的数组(数组 A)中的数字范围。 计数排序是一种稳定排序,运行时间为 Θ(n+k),其中 n 和 k 分别是数组 A(输入数组)和 C(计数数组)的长度。 为了使该算法有效,k 不能比 n 大很多。 在这种情况下,k 是 100,n 是 1000000。 回答2 在这些情况下,计数排序将是显而易见的选择。 是的,正确实施它应该具有线性复杂性。 回答3 如何只计算每个整数的出现,然后将它们全部打印出来。 听起来像 O(n) 回答4 我假设,你的意思是你想要实现一个小的 O(n); 那么桶排序将是最快的。 事实上,既然你知道整数的范围,那么使用桶排序就变成了一个计算可以在 O(n) 中完成的数字出现的问题,即线性时间。 所谓计数排序,只是桶排序的一个特例。 回答5 如果范围固定且很小(例如 1..100 :)),则使用计数排序会得到 O(N) 回答6 对于任何有兴趣的人,在阅读答案之前,我迅速将这段 Ruby 拼凑在一起: module Enumerable def counting_sort(k) reduce(Array.new(k+1, 0)) {|counting, n| counting
  • 使用合并排序计数反转(Counting Inversions Using Merge Sort [closed])
    问题 关闭。 这个问题无法重现或由错别字引起。 它当前不接受答案。 想要改善这个问题吗? 更新问题,使它成为Stack Overflow的主题。 6年前关闭。 改善这个问题 我已经在Python中制作了一个合并排序程序,并且该程序运行良好,但是我对其进行了修改,以计算涉及的反转次数,现在它给了我一个错误: 这是我的代码: def merge_list(left,right,c): result=[] i,j=0,0 while i < len(left) and j < len(right): if left[i] < right[j]: result.append(left[i]) print "Left result",result i=i+1 elif left[i] > right[j]: result.append(right[j]) print "Right result",result j=j+1 if right[j] < left[i] and i<j: c=c+1 result=result+left[i:] result=result+right[j:] print "Inversions: ",c return result,c def sort_and_count(lis,count): if len(lis)<2: return lis middle
  • 带有合并排序算法的倒数计数的 Javascript 实现(Javascript implementation of the inversion-counting with merge-sort algorithm)
    问题 我正在尝试使用 javascript 中的合并排序算法来实现倒置计数。 我在这个网站上找到了描述和伪代码。 我的实现是这样的: var mergeAndCount, sortAndCount; /* the merging routine @param List1 the first list to be merged @param List2 the second list to be merged */ mergeAndCount = function(List1, List2) { var count, outputList; outputList = []; count = 0; while (List1.length > 0 || List2.length > 0) { outputList.push(Math.min(List1[0], List2[0])); if (List2[0] < List1[0]) { count += List1.length; List2.shift(); } else { List1.shift(); } } outputList = outputList.concat(List1.concat(List2)); return { 'count': count, 'list': outputList }; }; /* count
  • 排序链表最快的算法是什么?(What's the fastest algorithm for sorting a linked list?)
    问题 我很好奇O(n log n)是否是链表可以做的最好的事情。 回答1 可以合理地预期,在运行时,您所做的任何事情都不会比O(N log N)好。 但是,有趣的部分是研究是否可以对它进行就地稳定排序,最坏情况下的行为等等。 Putty名气的Simon Tatham解释了如何使用合并排序对链接列表进行排序。 他总结了以下评论: 像任何自重排序算法一样,它的运行时间为O(N log N)。 因为这是Mergesort,所以最坏情况下的运行时间仍为O(N log N)。 没有病理病例。 辅助存储需求小且恒定(即排序例程中的一些变量)。 由于数组中链表的本质不同,Mergesort实现避免了通常与算法相关的O(N)辅助存储成本。 在C中还有一个示例实现,可用于单链表和双链表。 就像@JørgenFogh在下面提到的那样,big-O表示法可能会隐藏一些恒定因素,这些因素可能会导致一种算法由于内存局部性,项目数量少等原因而表现更好。 回答2 根据许多因素,将列表复制到阵列然后使用Quicksort实际上可能会更快。 之所以会更快,是因为数组的缓存性能要比链表好得多。 如果列表中的节点分散在内存中,则可能会在整个位置生成高速缓存未命中。 再说一次,如果数组很大,无论如何都会遇到缓存未命中的情况。 Mergesort可以更好地并行化,因此如果您要这样做,它可能是一个更好的选择。
  • 使用 Pandas 进行计数和排序(Count and Sort with Pandas)
    问题 我有一个用于值的数据框,形成一个文件,我通过该文件按两列分组,这些列返回聚合的计数。 现在我想按最大计数值排序,但是出现以下错误: 关键错误:'计数' 看起来 group by agg count 列是某种索引,所以不知道该怎么做,我是 Python 和 Panda 的初学者。 这是实际代码,如果您需要更多详细信息,请告诉我: def answer_five(): df = census_df#.set_index(['STNAME']) df = df[df['SUMLEV'] == 50] df = df[['STNAME','CTYNAME']].groupby(['STNAME']).agg(['count']).sort(['count']) #df.set_index(['count']) print(df.index) # get sorted count max item return df.head(5) 回答1 我认为您需要添加reset_index ,然后将参数ascending=False到 sort_values 因为sort返回: FutureWarning: sort(columns=....) 已弃用,使用 sort_values(by=.....) .sort_values(['count'], Ascending=False) df =
  • 算法学习总结(2)——温故十大经典排序算法
    一、什么是排序算法 1.1、排序定义 对一序列对象根据某个关键字进行排序。 1.2、排序术语 稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面;不稳定:如果a原本在b的前面,而a=b,排序之后a可能会出现在b的后面;内排序:所有排序操作都在内存中完成;外排序:由于数据太大,因此把数据放在磁盘中,而排序通过磁盘和内存的数据传输才能进行;时间复杂度: 一个算法执行所耗费的时间。空间复杂度:运行完一个程序所需内存的大小。 1.3、算法总结 ​ (注意:n指数据规模;k指“桶”的个数;In-place指占用常数内存,不占用额外内存;Out-place指占用额外内存) 1.4、算法分类 ​ 1.5、比较和非比较的区别 常见的快速排序、归并排序、堆排序、冒泡排序等属于比较排序。在排序的最终结果里,元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较,才能确定自己的位置。在冒泡排序之类的排序中,问题规模为n,又因为需要比较n次,所以平均时间复杂度为O(n²)。在归并排序、快速排序之类的排序中,问题规模通过分治法消减为logN次,所以时间复杂度平均O(nlogn)。比较排序的优势是,适用于各种规模的数据,也不在乎数据的分布,都能进行排序。可以说,比较排序适用于一切需要排序的情况。计数排序、基数排序、桶排序则属于非比较排序。非比较排序是通过确定每个元素之前
  • 有效地查找数组中元素的等级?(Efficiently finding the ranks of elements in an array?)
    问题 如何有效地确定数组中每个元素的等级(在平局的情况下进行平均)? 例如: float[] rank(T)(T[] input) { // Implementation } auto foo = rank([3,6,4,2,2]); // foo == [3, 5, 4, 1.5, 1.5] 我想到的唯一方法是分配3个数组: 输入数组的重复项,因为必须对其进行排序,并且我们不拥有该数组。 跟踪输入数组排序顺序的数组。 要返回的等级数组。 有谁知道如何在O(N log N)时间和O(1)辅助空间中执行此操作(这意味着我们必须分配的唯一数组是要返回的数组),或者至少摆脱了其中一个上面的三个数组? 回答1 您可以分配要返回的数组(将其称为R),将其初始化为0..n-1,然后使用输入I [R [k]]与I [R [j]]而不是普通的R [k]与R [j],然后根据需要交换R数组中的值(而不是照常替换I数组中的值)。 您可以使用quicksort或heapsort(或bubbleort来实现这种间接排序),但这会增加您的复杂性。 您只需要分配一个数组-并为索引分配一些堆栈空间。 回答2 好的,所以您将输入数组复制到foo 。 使用堆排序在O(n log n)时间内就地对foo进行排序。 现在,使用输入数组的第一个元素,并使用二进制搜索在O(log n)时间的foo中找到其等级
  • 使用命令行工具按排序顺序计算重复项(counting duplicates in a sorted sequence using command line tools)
    问题 我有一个命令 (cmd1),它通过日志文件 grep 过滤掉一组数字。 这些数字的顺序是随机的,所以我使用 sort -gr 来获得一个反向排序的数字列表。 此排序列表中可能存在重复项。 我需要找到该列表中每个唯一数字的计数。 例如,如果 cmd1 的输出是: 100 100 100 99 99 26 25 24 24 我需要另一个命令,我可以将上面的输出通过管道传输到,这样,我得到: 100 3 99 2 26 1 25 1 24 2 回答1 怎么样; $ echo "100 100 100 99 99 26 25 24 24" \ | tr " " "\n" \ | sort \ | uniq -c \ | sort -k2nr \ | awk '{printf("%s\t%s\n",$2,$1)}END{print}' 结果是: 100 3 99 2 26 1 25 1 24 2 回答2 uniq -c至少适用于 GNU uniq 8.23,并且完全符合您的要求(假设输入已排序)。 回答3 如果顺序不重要 # echo "100 100 100 99 99 26 25 24 24" | awk '{for(i=1;i<=NF;i++)a[$i]++}END{for(o in a) printf "%s %s ",o,a[o]}' 26 1 100 3 99 2 24 2
  • 计算数组中的反转(Counting inversions in an array)
    问题 我正在设计一种算法来执行以下操作:给定数组A[1... n] ,对于每个i < j ,找到所有求反对,使得A[i] > A[j] 。 我正在使用合并排序并将数组A复制到数组B,然后比较两个数组,但是我很难知道如何使用它来查找反转数。 任何提示或帮助将不胜感激。 回答1 所以这是Java中的O(n log n)解决方案。 long merge(int[] arr, int[] left, int[] right) { int i = 0, j = 0, count = 0; while (i < left.length || j < right.length) { if (i == left.length) { arr[i+j] = right[j]; j++; } else if (j == right.length) { arr[i+j] = left[i]; i++; } else if (left[i] <= right[j]) { arr[i+j] = left[i]; i++; } else { arr[i+j] = right[j]; count += left.length-i; j++; } } return count; } long invCount(int[] arr) { if (arr.length < 2) return 0; int m =
  • Python实现十大经典算法动画图解
    该文章摘自https://www.cnblogs.com/onepixel/articles/7674659.html#!comments 如有侵权,请联系邮箱459791796@qq.com,会及时删除 原文章为c语言实现,本文用python3实现 0、算法概述 0.1 算法分类 十种常见排序算法可以分为两大类: 比较类排序:通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此也称为非线性时间比较类排序。非比较类排序:不通过比较来决定元素间的相对次序,它可以突破基于比较排序的时间下界,以线性时间运行,因此也称为线性时间非比较类排序。 0.2 算法复杂度 0.3 相关概念 稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面。不稳定:如果a原本在b的前面,而a=b,排序之后 a 可能会出现在 b 的后面。时间复杂度:对排序数据的总的操作次数。反映当n变化时,操作次数呈现什么规律。空间复杂度:是指算法在计算机 内执行时所需存储空间的度量,它也是数据规模n的函数。 1、冒泡排序(Bubble Sort) 冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端
  • 为什么我们不能对普通数组应用计数排序?(Why we can not apply counting sort to general arrays?)
    问题 如果我们知道数组中的所有元素都以给定数字为上限,则使用线性时间就可以知道计数排序。 如果我们使用一个通用数组,我们是否只能在线性时间内扫描该数组,以找到该数组中的最大值,然后应用计数排序? 回答1 仅仅知道进行计数排序的上限还不够:您需要有足够的内存来容纳所有计数器。 当您遍历64位整数数组并发现最大元素为2 ^ 60时,请考虑一种情况。 这将意味着两件事: 您需要一个O(2 ^ 60)内存,并且将需要O(2 ^ 60)来完成排序。 O(2^60)与O(1)相同的事实在这里几乎没有帮助,因为常数因数太大。 对于伪多项式时间算法,这通常是一个问题。 回答2 假设最大数量是235684121。那么您将花费不可思议的RAM数量来保存存储桶。 回答3 我想提到一些@dasblinkenlight和@AlbinSunnanbo答案,您的想法是在O(n)传递中扫描数组,以找到数组中的最大值是可以的。 以下是维基百科的内容: 但是,如果k的值未知,则可以通过对数据进行附加循环来计算它,以确定在数据中实际出现的最大键值。 由于时间复杂度为O(n + k)并且k应该在某个限制之内,因此您发现的k应该很小。 正如@dasblinkenlight提到的那样, O(large_value)实际上不能收敛到O(1) 。 尽管到目前为止我还不知道Counting sort的任何主要应用
  • 几种排序算法简单的回顾(Java实现)
    1.简单的回顾一下排序算法。发现写代码的时候还是有很多错误的地方。 2.附上简单的图片说明和代码。(网图侵删) 3.代码在本地运行均已通过。 ========================================================== 1.冒泡排序(Bubble Sort) 2.插入排序(Insertion Sort) 3.选择排序(Selection Sort) 4.希尔排序(Shell Sort) 5.归并排序(Merge Sort) 6.快速排序(Quick Sort) 7.桶排序(Bucket Sort) 8.基数排序(Radix Sort) 9.计数排序(Counting Sort) 10.堆排序(Heap Sort) 1.冒泡排序(Bubble Sort) public static void main(String[] args) { int[] nums = {9, 5, 2, 7}; BubbleSort(nums, nums.length); System.out.println(Arrays.toString(nums)); } static void BubbleSort(int[] nums, int n) { for (int i = 0; i < n; i++) { boolean flag = false;//若无交换退出
  • 数据结构十大经典算法(面试常问)
    数据结构十大经典算法 一、算法的分类二、术语说明三、时间复杂度四、交换排序1、冒泡排序2、快速排序 五、插入排序3、插入排序(Insertion Sort)4、希尔排序(Shell Sort) 六、选择排序5、选择排序6、堆排序(Heap Sort) 七、归并排序7、归并排序 线性时间非比较类排序8、计数排序(Counting Sort)9、桶排序(Bucket Sort)10、基数排序(Radix Sort) 本篇参考以下三位博主写的博文 1、算法学习总结(2)——温故十大经典排序算法 2、排序算法整合(冒泡,快速,希尔,拓扑,归并) 3、史上最容易理解的《十大经典算法(动态图展示)》而整理出的一篇,可谓是集精华于一身的鸿篇巨制哈哈哈(开玩笑),还是乖乖学习吧 ♡ \color{red}{\heartsuit} ♡ 一、算法的分类 二、术语说明 ♢ \color{red}{\diamondsuit} ♢稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面; ♢ \color{blue}{\diamondsuit} ♢不稳定:如果a原本在b的前面,而a=b,排序之后a可能会出现在b的后面; ♢ \color{green}{\diamondsuit} ♢内排序:所有排序操作都在内存中完成; 外排序:由于数据太大,因此把数据放在磁盘中,而排序通过磁盘和内存的数据传输才能进行;
  • 计数排序的时间复杂度(The time complexity of counting sort)
    问题 我正在上一门算法课程,在那里我看到计数排序的时间复杂度是 O(n+k),其中 k 是数字范围,n 是输入大小。 我的问题是,当 k 和 n 之间的差异太大时,例如当 k=O(n 2 ) 或 O(n 3 ) 时,我们可以说复杂度是 O(n 2 ) 还是 O(n 3 ) ? 那么在这种情况下,计数排序不是一个明智的方法,我们可以使用归并排序。 我对吗? 回答1 是的,你在所有方面都是正确的。 此外,我们可以做出更有力的陈述:当 k=O(n 2 ) 或 O(n 3 ) 时,我们可以说计数排序的复杂度是 Θ(n 2 ) 或 Θ(n 3 )。 回答2 理论上,您仍然可以在 O(n) 时间内进行排序。 如果值的范围是 1 到 n 3,则转换为基数 n 并进行基数排序。 在基数 n 中,数字有 3 位,因此基数转换的运行时间为 O(3n + 3n) + O(n)。 总体 O(n)。