scala - 我的快速选择代码不能正常工作

Question

我的快速选择算法必须比seq.sort + seq(k). 我认为else if (low.length == 0) a(pivot)是错误的，我认为我的算法对于测试来说太慢了。

代码的一些结果：

Running performance tests on almost-sorted sequences
 Test 1
  quickSelect vs Arrays.sort: 0,0313 vs 0,0313
 Test 2
  quickSelect vs Arrays.sort: 0,0156 vs 0,0313
 Test 3
  quickSelect vs Arrays.sort: 0,0313 vs 0,0313
 Test 4
  quickSelect vs Arrays.sort: 0,0313 vs 0,0313
 Test 5
  quickSelect vs Arrays.sort: 0,0469 vs 0,0156

Testing quickSelect.find(List(1), 0)
Testing quickSelect.find(List(1, 1, 1, 1), 0)
Testing quickSelect.find(List(1, 1, 1, 1), 1)
Testing quickSelect.find(List(1, 1, 1, 1), 2)
Testing quickSelect.find(List(1, 1, 1, 1), 3)
Testing quickSelect.find(List(1, 2, 3), 0)
Testing quickSelect.find(List(1, 2, 3), 1)
- should compute correct results on some selected inputs *** FAILED ***
  1 was not equal to 2

  val rand = new scala.util.Random(21)

def find(seq: Seq[Int], k: Int): Int = {
  require(0 <= k && k < seq.length)
  val a: Array[Int] = seq.toArray[Int]
  val pivot = rand.nextInt(a.length)     
  val (low, high) = a.partition(_ < a(pivot))
  if (low.length == k-1) a(pivot)
  else if (low.length == 0) a(pivot)
  else if (low.length <= k) find(high, k - low.length)
  else find(low, k) 
}