Scala 2.12：对含占位符的Double列表排序并保留占位符位置

核心思路分两步：先提取所有非占位符元素排序，再将排序后的元素按原列表的非占位符位置依次填充，占位符位置保持不变。

实现代码 #

val placeholder = Double.NaN
val input = List(placeholder, 5.0, 2.0, placeholder, 4.0, 3.0, placeholder)

// 定义占位符判断逻辑（适配Double.NaN的特殊性）
def isPlaceholder(d: Double): Boolean = java.lang.Double.isNaN(d)

// 提取非占位符元素并升序排序
val sortedNonPlaceholders = input.filter(!isPlaceholder(_)).sorted

// 用迭代器高效填充排序后的元素
val sortedIter = sortedNonPlaceholders.iterator
val result = input.map {
  case elem if isPlaceholder(elem) => elem
  case _ => sortedIter.next()
}

println(result) // 输出: List(NaN, 2.0, 3.0, NaN, 4.0, 5.0, NaN)

关键细节说明 #

• 针对Double.NaN的特殊性：NaN == NaN返回false，因此不能直接用==判断占位符，必须用java.lang.Double.isNaN方法识别。
• 如果使用自定义占位符（如-1.0），只需修改isPlaceholder函数的判断逻辑，例如d == -1.0即可。
• 使用iterator是为了避免重复遍历排序后的列表，提升填充过程的效率。

复杂度分析 #

• 排序步骤时间复杂度为O(m log m)（m为非占位符元素数量），遍历填充步骤为O(n)（n为原列表长度），整体效率较高。

内容的提问来源于stack exchange，提问作者Niklas2501