问题标签 [sorting]

我经常需要按值对字典（由键和值组成）进行排序。例如，我有一个单词哈希和我想按频率排序的相应频率。

有一个SortedList对单个值（比如频率）有好处的，我想映射回这个词。

SortedDictionary按键排序，而不是按值排序。有些人求助于自定义类，但有更清洁的方法吗？

我正在寻找一种简单的算法来“序列化”有向图。特别是我有一组文件，它们的执行顺序相互依赖，我想在编译时找到正确的顺序。我知道这一定是一件相当普遍的事情——编译器一直都在这样做——但我的 google-fu 今天一直很弱。什么是“首选”算法？

I was recently brushing up on some fundamentals and found merge sorting a linked list to be a pretty good challenge. If you have a good implementation then show it off here.

假设我们有一个用伪语言定义的简单函数。

我们传入一个未排序的数字列表和一个指定升序或降序排序的布尔值。作为回报，我们得到一个排序的数字列表。

根据我的经验，有些人比其他人更擅长捕捉边界条件。问题是，“你怎么知道你什么时候'完成'捕获测试用例”？

我们现在可以开始列出案例，一些聪明的人无疑会想到以前没有涵盖的“再一个”案例。

我想使用升序对数组进行排序C/C++。结果是一个包含元素索引的数组。每个索引对应于排序数组中的元素位置。

例子

编辑：我正在使用 shell 排序程序。重复值索引是根据原始数组中首先出现的重复值来任意选择的。

更新：

尽管我尽了最大努力，但我仍然无法为指针数组实现排序算法。当前示例无法编译。

有人可以告诉我有什么问题吗？

我非常感谢一些帮助！

所以我今天遇到了一个有趣的问题。我们有一个返回 IList 的 WCF Web 服务。在我想对其进行排序之前，这没什么大不了的。

原来 IList 接口没有内置排序方法。

我最终使用该ArrayList.Adapter(list).Sort(new MyComparer())方法来解决问题，但对我来说它似乎有点“贫民窟”。

我玩弄了编写扩展方法，也继承了 IList 并实现了我自己的 Sort() 方法以及强制转换为 List，但这些似乎都不是过于优雅。

所以我的问题是，有没有人有一个优雅的解决方案来排序 IList

我为我的娱乐写了一个 O(n!) 排序，如果不完全替换它，就不能简单地优化它以更快地运行。[不，我不只是在物品被分类之前随机化这些物品]。

我如何编写更糟糕的 Big-O 排序，而不只是添加可以拉出以降低时间复杂度的无关垃圾？

http://en.wikipedia.org/wiki/Big_O_notation具有按增长顺序排序的各种时间复杂度。

编辑：我找到了代码，这是我的 O(n!) 确定性排序，带有有趣的 hack 以生成列表的所有组合的列表。我有一个稍微长一点的 get_all_combinations 版本，它返回一个可迭代的组合，但不幸的是我不能让它成为一个单一的语句。[希望我没有通过修复错别字和删除以下代码中的下划线来引入错误]

对相同的输入使用相同的排序命令会在不同的机器上产生不同的结果。我该如何解决？

我们有一个大型数据库，在该数据库上进行 DB 端分页。这很快，在几分之一秒内从数百万条记录中返回一页 50 行。

用户可以定义自己的排序，基本上是选择要排序的列。列是动态的——一些具有数值、一些日期和一些文本。

虽然大多数按预期排序，但文本以一种愚蠢的方式排序。好吧，我说愚蠢，这对计算机有意义，但会让用户感到沮丧。

例如，按字符串记录 id 排序会给出如下结果：

...等等。

我希望这考虑到这个数字，所以：

我无法控制输入（否则我只会在前导 000 中格式化）并且我不能依赖单一格式 - 有些是“{alpha code}-{dept code}-{rec id}”之类的东西。

我知道在 C# 中有几种方法可以做到这一点，但不能拉下所有记录来对它们进行排序，因为那样会很慢。

有谁知道在 Sql server 中快速应用自然排序的方法？

我们正在使用：

然后我们按那个分页。

我们可以添加触发器，尽管我们不会。他们所有的输入都是参数化的等等，但我不能改变格式——如果他们输入“rec2”和“rec10”，他们希望它们会像那样以自然顺序返回。

我们有有效的用户输入，针对不同的客户遵循不同的格式。

一个人可能会去 rec1, rec2, rec3, ... rec100, rec101

而另一个可能会去：grp1rec1，grp1rec2，... grp20rec300，grp20rec301

当我说我们无法控制输入时，我的意思是我们不能强迫用户更改这些标准 - 它们具有像 grp1rec1 这样的值，我不能将其重新格式化为 grp01rec001，因为这会改变用于查找和链接到外部系统。

这些格式变化很大，但通常是字母和数字的混合。

在 C# 中对这些进行排序很容易 - 只需将其分解为{ "grp", 20, "rec", 301 }然后依次比较序列值。

但是可能有数百万条记录并且数据是分页的，我需要在 SQL 服务器上进行排序。

SQL 服务器按值排序，而不是比较 - 在​​ C# 中，我可以将值拆分出来进行比较，但在 SQL 中，我需要一些逻辑来（非常快速地）获得一致排序的单个值。

@moebius - 您的答案可能有效，但为所有这些文本值添加排序键确实是一种丑陋的妥协。

如何在不同的编程语言中自然地对字符串数组进行排序？在答案中发布您的实现及其使用的语言。