我一直在学习排序。大多数排序算法(合并、快速等)都使用数组。
我在想如果我没有对数组进行排序会怎么样
我想到的算法是
- 遍历数组中的每个元素- 0 (n)。
- 对于每个元素，将其与双链表的开始元素和结束元素进行比较。
- 将元素添加到链表中的正确位置。(从列表的开始/结束开始迭代，基于哪个更快)。
- 当原始数组中的所有元素排序后，创建后台线程将它们复制到数组中。在复制完成之前，通过遍历list返回索引元素。
- 复制完成后，通过数组索引返回元素。
现在，它的时间复杂度是多少，我如何计算它?
让我们一步一步来。
遍历数组O(n)中的每个元素
是的!
对于每个元素，将该元素与双链表的起始元素和结束元素进行比较。
将元素添加到链表中的正确位置。(从list的Start/end开始迭代，基于哪个更快)。
让我们假设双链表中目前有k个元素。不幸的是，仅仅通过查看列表的前后元素，您将无法判断该元素可能在列表中的位置。很有可能您的元素在值上更接近列表的前元素，而不是后元素，但实际上应该位于后元素之前。在链表中也没有随机访问，所以在最坏的情况下，你可能不得不扫描链表中的所有k个元素，试图找到这个元素所属的位置。这意味着在最坏的情况下所做的功是O(k)现在，算法的每次迭代都会使k(列表中元素的数量)增加1，所以在最坏的情况下完成的工作是1 + 2 + 3 +…+ n = Θ(n2).
当原始数组中的所有元素排序后，创建后台线程将它们复制到数组中。在复制未完成之前，通过遍历list返回索引元素。
复制完成后，通过数组索引返回元素。
这是一个有趣的想法，很难衡量其复杂性。如果后台线程耗尽或者非常慢，那么查找任何元素的成本在最坏的情况下将是O(n)，因为您可能必须扫描列表中一半以上的元素才能找到您要查找的元素。
总的来说，你的算法运行时间为O(n2)，并使用Θ(n)内存。它本质上是插入排序的一种变体(正如@Yu Hao所指出的)，在实践中，我预计这将比使用标准的O(n log n)排序算法，甚至是就地插入排序要慢得多，因为链表提供了额外的内存开销和糟糕的引用位置。
你描述的算法基本上是插入排序的一个变体。
这里使用链表的主要原因是为了避免数组中额外的元素交换。如果有的话，比较具有双链表的头和尾的元素可以提供较小的性能改进。
对于随机输入，时间复杂度仍然是O(N2)