-2

我有一个伪代码算法，它将一个未排序的数组作为输入并将其排序在一个链表中。我不太明白它是如何工作的。也许其中有一个错误。我已经尝试了一个多小时来了解它是如何工作的，但我被困在某个点上。我会尽可能多地解释。任何知道它是如何工作的人都很乐意提供帮助。

ORDER(A)
head [L1] = create();    //Null List is created.
key[head[L1]] = A[1];    //First element of the array is put as the first in list.

for i=2 to length(A);
    x = create();        // create a node for every element of the array
    key[x] = A[i];       // put A[i] as key in the node.
    p1 = head[L1];       // make p1 head of the list.
    if key[p1] > A[i];       //compare A[i] with the head
       insert_head(x);      // if smaller put it in the beggining and make it head
    while key[next[p1]] < A[i] AND next[p1] =/= nil  // This part I don't understand 
       if next[p1] == nil                               //very well.
          next[p1] = x
          next[x] = nil
       else
          next[x] = next[p1]
          next[p1] = x;
4

2 回答 2

3

它与插入排序非常相似。

链表已排序并从空开始，然后将数组中的每个元素插入到链表中的正确位置，以便在每次插入后对其进行排序。

对于插入，它会遍历链表，直到我们要插入的元素小于链表中的当前元素，或者我们已经到达链表的末尾，然后再插入。

我确实认为可能存在错误，我认为while循环应该是：

// here we advance the position in the linked-list
//   until we reach the end or the current element is smaller
while key[next[p1]] < A[i] AND next[p1] =/= nil
  p1 = next[p1]

// if we reached the end, next[x] won't point to anything
if next[p1] == nil                          
  next[p1] = x
  next[x] = nil
// if we didn't reach the end,
//   next[x] needs to point to anything what next[p1] was pointing to
else
  next[x] = next[p1]
  next[p1] = x;
于 2013-10-22T13:24:49.117 回答
1

您拥有的伪代码是插入排序的实现，它的最坏情况复杂度为 O(n^2)。

基本上，while 块正在循环保存已排序数据子集的整个列表，当 while 找到要插入的位置时，它将其插入到已排序列表中。如果 while 没有找到要插入的位置，则将其插入到列表的末尾。

也许您应该考虑使用合并排序（复杂度 O(n log-n)），然后将其传递给列表（O(n)）

这个提议的总复杂度是 O(n log n)

于 2013-10-22T13:58:39.003 回答