javascript - 排序 javascript 挂起

Question

我正在渲染大约 3000 条记录，

我正在使用这个排序开源脚本，

当我单击该列时，我的浏览器很快就会挂起，

我无法继续，

这个问题有解决办法吗？

link text

Answer 1

更新 2

我已将更新发送给上述代码的原作者，但在他决定发布之前，here is my updated version .如果您决定这样做，它会加快标准内置 sort() 的使用。它还用稳定的归并排序取代了稳定的鸡尾酒排序。在我的测试中，合并排序几乎与使用 sort() 一样快。希望对您有所帮助。

更新

就内置的 sort() 函数而言，我不再认为浏览器之间存在很大差异。例如，虽然 IE8 总体上比 Chrome 慢得多，但我认为这不仅仅与排序功能有关。我使用一些随机数据在 IE8 中做了一些分析。我发现当列数据是数字或日期时，原始代码可以得到相当大的改进。将正则表达式搜索放在这些数据类型的比较函数中会大大降低速度，因为每次在元素之间进行比较时都会进行这些搜索，对于 3000 个元素，大约需要 60,000 次比较。正则表达式的数量是它的两倍。通过在开始排序之前执行所有这些操作，我们执行了 3,000 个正则表达式而不是 120,000 个。这可以节省大约 50% 的时间。我稍后会提交对可排序代码的更改。

除此之外，大部分时间是重新排序周围的 DOM 元素，而不是排序(除非您使用摇床排序)。如果你能找到一种更快的方法来做到这一点，那么你可以在那里节省一些时间，但我不知道有什么方法可以做到这一点。

原答案:

这里的问题可能与实际排序有关。如果您在那里取消注释某些代码(并注释掉一些其他代码)，那么您的代码正在使用摇床排序来获得稳定排序。 Shaker 排序本质上是一种双向冒泡排序。冒泡排序非常慢，O(N^2)。如果您没有取消注释该代码，那么它正在使用 javascript 的内置 sort() 函数和各种比较器函数。问题是这个 sort() 函数是 implemented differently in different browsers所以你可能想看看这个问题是否发生在某些浏览器中而不是其他浏览器中。显然，Webkit 代码仍然使用选择或最小排序，即 O(N^2)。这几乎让我想哭。您使用什么浏览器对此进行了测试？

如果排序函数最终证明是问题所在，那么您可以尝试更改上面的代码以使用合并排序或快速排序，它们都是 O(N log N)。为了避免 O(N^2) 情况，快速排序有点棘手，因此您可能希望坚持使用合并排序。此外，合并排序是一种稳定排序。 This page有一个示例可以帮助您开始使用归并排序。