问题标签 [radix-sort]

MySQLquicksort在用户请求时对结果集进行排序。现在平均而言，quicksort效率为O(Nlog N)，这是可以接受的（即使它最坏的情况有时可能达到O(N^2)。现在对于大多数情况来说这很好，但想象一下我有一个列，比如说，pin-number，它总是有 6 位数字。并且一个特定的查询会获取数百万行并根据该键对它们进行排序。在这种情况下radix-sort，给出线性顺序不是更好的选择吗？有什么办法（也许写一个插件或其他东西）我可以引入一个新的MySQL 函数，比如说myorderby，它将通过我定义的自定义基数排序基于给定键对结果集进行排序？其次，这个调整是否值得？

我想使用队列创建一个基数排序实现。

我不知道我的代码的哪一部分有问题或者我应该阅读哪些资源。我的代码可能完全错误，但这是我没有任何帮助的实现（我还没有上过数据结构和算法课程）。

我创建了一个函数，但它不起作用。在进行研究时，我看到了一些代码示例，但它们对我来说似乎更复杂。

首先我想找到所有整数的最低有效位 然后将它们排序到下标匹配的队列元素中， 然后在排序后将所有队列复制到第 11 个队列元素的末尾。再次在第 11 个队列元素中进行此排序，直到达到最高有效位。

我可以找到最低有效数字。并按照这个数字排序。但是，我无法分析其他数字。例如; 我可以对 1, 2 , 4, 5, 3 进行排序，但是当需要对 2 个或更多数字进行排序时，它会失败......

我希望，我很清楚并简要解释了我的问题。

编辑1（取得了一些进展）

我听从了威廉·莫里斯的建议。我不得不在 CodeReview 上问同样的问题，他给了我一些说明，让我的代码更清晰。

我将我的函数划分为函数，并且也停止使用递归。

首先，我创建了一个 add_to_q 函数，它为相关队列增加了价值，它有助于摆脱代码重复。顺便说一句，James Khoury 的方法是最简单的，但它再次使用递归。

其次，我创建了其他辅助函数。一个是 add_to_eleventh，它简单地将所有队列元素添加到第十一个队列的后面。在我看来，它正在做问题想要的事情。

第三，我的最后一个辅助函数是 back_to_ints。其目的是将第 11 个队列中的元素除以 10 并以整数数组的形式返回。

最后，我的新排序函数现在对同一位数的整数进行排序。这样，数字[7] = {112,133,122,334,345,447,346};

我部分解决了这个问题。如果您想对相同数字的数字进行排序，它可以工作。否则，它会失败。例如，您的输入是 112,133,122,334,345,447,346 那么结果将是112 122 133 334 345 346 447。但是，如果用户想要对类似的东西进行排序（111,13,12,334,345,447,1），它会给出111 1 12 13 334 345 447。那么，我该如何克服这个问题。

另外，我已经稍微更改了我的头文件。

感谢您重新打开我的线程...

Timsort、Quicksort 和 Mergesort 等算法主导着“现实世界”的排序方法。这些比较排序的案例非常实用——它们已被证明是各种环境中性能最高、最稳定、多用途的排序算法。

然而，我们在计算机上排序的几乎所有东西似乎都是可数/部分有序的。数字、字符、字符串，甚至函数都适用于一些有意义的非比较排序方法。这里的一个候选者是基数排序。一般来说，它会比 O(n*log(n)) 表现得更快，在许多复杂度为 O(K*n) -- K 的情况下，大大超过了 n * log(n) 的理论比较排序限制是表示特定项目所需的位数。

是什么赋予了？

我已经阅读了基数排序的实现，它适用于小于十的 int 数据类型，即它们由一个 sig-fig 代替。（例如 1, 0, 3, 4, 9,... 只是为了清楚）。这个实现并不太难，但是大于 10 的数字呢？如何在第一遍仅比较一个位的数字，然后在第二遍的十位数字进行比较，依此类推，而无需将数组元素显式转换为字符串或字符类型。（或者这只是必要的？）

我不知道如何从队列数组中删除值并使用基数排序将它们放入整数数组中。

这是我现在拥有的代码：

place 是一个应该为 (1,10,100,1000,100000) 的 int，它指的是 6 位数字中的位置，例如 place = 1 in 684720 从 selectDigit 返回的数字将为 0（第 1 位）和等 selectDigit 采用参数（int digit，int place）。现在我有一个空数组 arr，其中每个索引都包含一个空数组队列。对于数组中的每个数字 a，我将正确的 1s、10s、100s 等值添加到 arr[i] 的正确索引中。在这部分中，我不确定是否应该将队列中的每个值移回数组中，但我不确定如何实现这一点。

编辑：上面的修改后的代码产生以下输出（仍然不正确），它基本上在 a 的每个索引中都有最后一位（排序前），但不是 10s、100s、1000s 等位置。

如何将每个元素添加到数组队列中？基本上，如果我有一个队列数组，其中每个索引都是一个数组队列，其中包含 1、10、100 等，将相应的 6 位数字放在数组 a 的另一个索引中。例如，如果 a[1] 是 123456，那么我怎样才能使下面的代码保持 arr[1] 654321？我之前发布过一个与此类似的问题，但我只是想解决这个问题。

使用从互联网上某处获取的代码，我尝试在我的程序中实现基数排序功能。该程序的输入是一个包含大约 120 万个长整数的文本文件。我已经有一个 maxSize = 1200000 的数组，它存储来自文本文件的整数，所以当我在 radixSort 函数中创建工作数组时，我得到了一个段错误。有什么办法可以避免这种情况吗？

这是驱动程序代码：

这是功能

另外，创建数组的 main 的摘录：

并确定大小：

我正在尝试使用列表实现基数为 256 的基数排序。排序工作正常，但对大数组进行排序需要很长时间，此外复杂性应该是线性的，O(n)，但我没有得到那个结果，因为我正在对输出中的排序进行计时。这是我的代码：

插入功能：

删除功能：

Radix_Sort 函数：

主要的：

谁能看到，也许我正在做一些需要大量时间执行的不必要的操作？

您好我想了解基数排序的逻辑，我指的是维基百科的代码。这是接收数组的排序的排序函数，以及元素的数量。虽然代码运行得很好，但我无法理解代码的逻辑。在 while 循环中，我们首先初始化一个 10 位的桶数组，其中包含 1 的数量，以及数组的第一个和第二个索引的 2。但在那之后，很难理解它想要做什么。

谁能帮我这个？谢谢

我编写了这段代码来实现字符串的 lsd 基数排序算法。

逻辑：我们从最低有效位开始，首先对这个数字进行排序。然后，我们移动到左边的下一个数字，依此类推。count[]包含每个英文字母在特定数字位置的频率。count[1]表示'a', count[2]of ...的频率'b'...等等... 和count[0]=0. 然后，我们计算累积计数。现在我们再次遍历字符串数组并计算数组中的适当位置aux。例如：如果count[2] = 4和count[1]=1对于特定的数字位置，这意味着'b'在该位置的单词将占据aux[1], aux[2], aux[3]。

代码在此处和此处打印后会出现段错误。问题出在第三个“for j”循环中。任何人都可以找出问题吗？