高效排序

Question

10

我有一个值数组，它几乎被排序了，但是有一些值错位（例如在100000个值中有50个错位）。如何最有效地对其进行排序？

- algo-geeks

你可以在标签中加入“算法”。也许它们也能帮上忙。 - Neilvert Noval

1

你的价值观是什么？简单整型或浮点型，还是结构体？你对效率的衡量标准是什么？空间还是时间？ - rotoglup

1

伙计，你真的需要回去复习一下你的问题并接受一些答案。 - karlphillip

5个回答

1

使用插入排序，当接近有序数组时，它是一个非常好的选择，因为对于它们来说时间复杂度接近O(n)。实际上我相信.NET框架在内部使用插入排序对枚举值进行排序（因为它们经常是有序的），尽管我需要重新检查一下。

- user541686

0

我的第一反应是识别错位的元素并将它们移动到一个单独的数组中，在那里使用任何你喜欢的算法进行排序（由于数量很少，所以不应该有影响），然后再合并排序回来。

- R.. GitHub STOP HELPING ICE

找出数组中未排序的“程度”（因此也就是“错位”的元素）实际上很难，据我所知...你知道任何好的算法吗？ - user541686

请提出一种寻找所谓“错位元素”的算法。谢谢。 - NPE

0

找到最佳的排序算法取决于您对数据的控制程度。

排序算法被归类为插入、交换、选择、合并等方法。这意味着如果您可以控制插入新数据的机制，则可以在此过程中对它们进行排序。如果只能在数据到位后对数组进行排序，那么最适合此操作的算法完全不同。

无论如何，这些都是有趣的阅读材料：

- karlphillip

0

现在，大多数libc实现提供的qsort或mergesort函数已经以高效的方式处理了这种特殊情况。

因此，请阅读您的libc文档，或者更好地，检查它如何实现排序（如果您可以访问源代码），因为有时这是一个未在文档中说明的实现细节！

- salva

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Milan · Accepted Answer

在数组几乎排好序的情况下，可以使用以下排序算法之一：

Smoothsort

维基百科上甚至有它的Java实现。由于您无法比O（n）更快地排序（因为即使要找出数组是否已排序需要那么长时间），所以Smoothsort是一个不错的选择。更多详情请点击此处。

如果输入已经被部分排序，Smoothsort的优点在于它可以接近O（n）的时间。

鸡尾酒排序在大O符号表示法中的复杂度在最坏情况和平均情况下都是O（n²），但如果在应用排序算法之前列表已经大部分排序，则它会趋近于O（n）。

Java 7中的数组现在实际上正在使用timsort来对对象进行排序（sort()）。关于timsort的描述点击此处。