1

我承认我的算法知识不是很好。我使用基本递归在 R 中编写了一个快速排序函数。我的问题是，如何修改此算法以在每次迭代之间也显示中间向量。我知道有一种聪明的方法可以跟踪你的支点在哪里，但我自己很难弄清楚。

qs <- function(vec) {

  if(length(vec) > 1) {

    pivot <- vec[1]

    low <- qs(vec[vec < pivot])
    mid <- vec[vec == pivot]
    high <- qs(vec[vec > pivot])

    c(low, mid, high)


  }

  else vec

}
4

3 回答 3

1

PS：我不确定，但是您的实现可能效率很低，具体取决于 R 如何使用逻辑数组实现下标。

如果不在当前状态下花费太多内存（即使用递归），您就无法做到这一点。

如果你想保持递归： 这是深度优先的方法。初始化一个数组数组。第一个索引是深度，相应的数组将为您提供该深度的状态。跟踪深度（即传递深度作为参数）并将子数组附加到相应的深度。

代码：

printableList = Array of empty arrays 
qs <- function(vec, depth) {
printableList[depth] = printableList[depth] + vec

  if(length(vec) > 1) {
    pivot <- vec[1]
    low <- qs(vec[vec < pivot], depth+1)
    mid <- vec[vec == pivot]
    high <- qs(vec[vec > pivot], depth+1)

    c(low, mid, high)
  }
  else vec
}

或者： 您也可以将整个事情实现为广度优先方法。您将不得不使用队列来实现整个事情。在这里，由于您逐层处理子问题，您只需打印它们。

于 2013-07-11T23:04:45.460 回答
0

您可以通过在每个函数调用中传递整个向量以及“start”和“end”参数来描述您当前正在排序的向量切片。这是我第一次尝试这样做。也许你可以写一个更优雅的版本？

qs<-function(vec,start=1,finish=length(vec)) {
  if (finish>start) {
    pivot<-vec[start]
    N<-length(vec)
    window<-((1:N)>=start) & ((1:N)<=finish)
    low_part<-vec[(vec<pivot) & window]
    mid_part<-vec[(vec==pivot) & window]
    high_part<-vec[(vec>pivot) & window]

    if (start>1) cat(vec[1:(start-1)],"| ")
    cat(low_part,">>>",mid_part,"<<<",high_part)
    if (finish<N) cat(" |",vec[(finish+1):N])
    cat("\n")

    vec[window]<-c(low_part,mid_part,high_part)
    if (length(low_part)>0) {
      low_top<-start+length(low_part)-1
      vec[start:low_top]<-qs(vec,start,low_top)[start:low_top]
    }
    if (length(high_part)>0) {
      high_bottom<-finish-length(high_part)+1
      vec[high_bottom:finish]<-qs(vec,high_bottom,finish)[high_bottom:finish]
    }
  }
  return(vec)
}

qs(sample(1:30,replace=TRUE))
于 2013-08-02T14:27:47.387 回答
0

正如@dickoa 指出的那样，使用print. 但是，如果您使用的是 GUI，则默认情况下会缓冲打印输出，直到函数返回。您可以使用 强制打印输出立即发生flush.console。

qs <- function(vec) {

  # print input vector
  print(vec); flush.console()

  if(length(vec) > 1) {

    pivot <- vec[1]

    low <- qs(vec[vec < pivot])
    mid <- vec[vec == pivot]
    high <- qs(vec[vec > pivot])

    c(low, mid, high)


  }

  else vec

}

样品运行：

> z <- sample(10)
> qs(z)
 [1]  2  6  1  4  8  5  9  7  3 10
[1] 1
[1]  6  4  8  5  9  7  3 10
[1] 4 5 3
[1] 3
[1] 5
[1]  8  9  7 10
[1] 7
[1]  9 10
integer(0)
[1] 10
 [1]  1  2  3  4  5  6  7  8  9 10
于 2013-07-12T01:38:45.397 回答