use*_*934 1 arrays sorting algorithm
我正在参加edx的cs50课程并且正在做pset3的黑客版本(实质上它是高级版本).基本上,程序将一个值作为命令行参数进行搜索,然后要求在数组中使用一堆数字.然后它对该数组进行排序和搜索,以获取在命令行输入的值.程序的实现方式,它使用伪随机数生成器来提供数组的数字.
任务是编写搜索和排序功能.我已经有了搜索功能,但排序功能应该是O(n).在常规版本中,您应该使用O(n ^ 2)算法,这不是一个实现的问题.同样使用log n算法也不是问题.但问题集特别要求提供一个大的O(n)算法.
它提示说,因为数组中的数字不会为负数,并且不大于LIMIT(生成器输出的数字是模数,因此它们不大于65000).但是,这有助于将算法变为O(n)？
但计数排序算法,声称是一个可接受的解决方案,返回一个新的排序数组,而不是实际排序原始的数组,这与pset规范相矛盾,因为这个返回类型的void暗示,此函数不能返回排序数组; 它必须通过绕过其中的值来"破坏性地"对它所传递的实际数组进行排序.
此外,如果我们决定使用另一个循环将已排序的数组复制到原始数组上,并且有很多连续的循环,我不确定排序函数是否可以被认为具有O(n)的运行时间.这是实际的pset,问题是关于排序部分.
任何关于如何实现这种算法的想法都将非常感激.没有必要提供实际的代码,而只是你可以在提供的条件下创建O(n)算法的逻辑.