在Scala中按部分訂單進行排序

Question

Partially sorting collections in Scala詢問如何用Scala中的PartialOrdering進行排序。評論指出作者不應該在給出的例子中進行部分排序。 I 做需要通過偏序排序 - 我有可能是其他國家的飛地的國家，這導致了部分排序。

因此：給定List[T]，其中T延伸PartialOrdering[T]，是否有根據偏序排序的明智方法？

Answer 1

我自己寫了一個適當的排序。像這樣的例子總是讓我覺得我錯過了標準的庫函數。

def sortByPartialOrdering[T](ts: Array[T], lessThan: (T, T) => Boolean): ListBuffer[T] = { 
    val len = ts.size 
    val visited = Array.fill[Boolean](len)(false) 
    val postOrder = ListBuffer.empty[Int] 

    def visit(n: Int): Unit = { 
     visited(n) = true 
     for (i <- 0 until len) 
     if (!visited(i) && lessThan(ts(i), ts(n))) 
      visit(i) 
     postOrder += n 
    } 

    for (i <- 0 until len) 
     if (!visited(i)) 
     visit(i) 

    assert(postOrder.size == len) 

    postOrder map ts 
    } 

評論/改進將受到歡迎 - 我不寫這麼多斯卡拉。