R中的合并排序使用列表而不是向量

Question

因此，我编写了这个基本代码，使用著名的合并排序算法对列表进行排序，我定义了两个函数mergelist，它比较和合并元素，并将列表划分为单个元素：

mergelists <- function(a,b) {
al <- length(a)
bl <- length(b)
r <- numeric(al+bl)
ai <- 1
bi <- 1
j <- 1
while((ai<=al) && (bi<=bl)) {
if(a[ai]<b[bi]) {
r[j] <- a[ai]
ai <- ai+1
} else {
r[j] <- b[bi]
bi <- bi+1
}
j <- j+1
}
if(ai<=al) r[j:(al+bl)] <- a[ai:al]
else if(bi<=bl) r[j:(al+bl)] <- b[bi:bl]
return(r)
}


mergesort <- function(x) {
l <- length(x)
if(l>1) {
p <- ceiling(l/2)
a <- mergesort(x[1:p])
b <- mergesort(x[(p+1):l])
return(mergelists(a,b))
}
return(x)
}

对于我到目前为止使用的示例来说，这似乎很好，例如：

> mergesort(c(11,10,9,15,6,12,17,8,19,7))
[1] 6 7 8 9 10 11 12 15 17 19

为了我正在做的一些研究，我想修改这段代码以处理R-列表而不是向量，列表通常定义如下：

> list(number=10,data=c(10,5,8,2))
$number
[1] 10
$data
[1] 10 5 8 2

数据表示这里的向量和数字是比较数。在改变之后，我想程序应该给我这样的东西：

>mergelists(list(number=8,data=c(1,3,5,8,9,10)),list(number=5,data=c(2,4,6,7)))
$number
[1] 20
$data
[1] 1 2 3 4 5 6 7 8 9 10

> mergesort(c(11,10,9,15,6,12,17,8,19,7))
$number
[1] 22
$data
[1] 6 7 8 9 10 11 12 15 17 19

这里的20基本上是8+5+ 7，因为合并这两个排序列表需要7个比较项，但我不知道如何做到这一点，因为我对R-列表有一点经验。我很感谢你的帮助。谢谢。

Answer 1

任何向量vec的起点都是list(number = 0, data = vec)，其中number为0，因为从未排序的向量开始需要进行0的比较。

您首先需要修改mergelists来处理两个列表，只需添加索引，然后在最后修改列表。

mergelists <- function(a,b) {
  firstn <- a$number + b$number
  a <- a$data
  b <- b$data
  al <- length(a)
  bl <- length(b)
  r <- numeric(al+bl)
  ai <- 1
  bi <- 1
  j <- 1
  while((ai<=al) && (bi<=bl)) {
    if(a[ai]<b[bi]) {
      r[j] <- a[ai]
      ai <- ai+1
    } else {
      r[j] <- b[bi]
      bi <- bi+1
    }
    j <- j+1
  }
  if(ai<=al) r[j:(al+bl)] <- a[ai:al]
  else if(bi<=bl) r[j:(al+bl)] <- b[bi:bl]
  return(list(number = firstn + j - 1L, data = r))
}
mergelists(list(number=8,data=c(1,3,5,8,9,10)), list(number=5,data=c(2,4,6,7)))
# $number
# [1] 20
# $data
#  [1]  1  2  3  4  5  6  7  8  9 10

既然定义了“基本函数”，就需要调用函数来生成增强向量(list)并相应地传递它。这个函数可以很容易地提高效率，但是我认为它的递归特性是健全的。

mergesort <- function(x) {
  # this first guarantees that if called with a vector, it is list-ified,
  # but if called with a list (i.e., every other time in the recursion),
  # the argument is untouched
  if (! is.list(x)) x <- list(number = 0, data = x)
  l <- length(x$data)
  if (l > 1) {
    p <- ceiling(l/2)
    # the `within(...)` trick is a sneaky trick, can easily be
    # handled with pre-assignment/subsetting
    a <- mergesort(within(x, { data <- data[1:p]; }))
    b <- mergesort(within(x, { data <- data[(p+1):l]; }))
    return(mergelists(a,b))
  }
  return(x)
}
mergesort(c(11,10,9,15,6,12,17,8,19,7))
# $number
# [1] 22
# $data
#  [1]  6  7  8  9 10 11 12 15 17 19