用scala写一个归并排序

很高兴回答你的问题。以下是使用 Scala 编写归并排序的示例代码：

object MergeSort {
  def merge(left: List[Int], right: List[Int]): List[Int] = (left, right) match {
    case (Nil, right) => right
    case (left, Nil) => left
    case (leftHead :: leftTail, rightHead :: rightTail) =>
      if (leftHead < rightHead) leftHead :: merge(leftTail, right)
      else rightHead :: merge(left, rightTail)
  }

  def sort(list: List[Int]): List[Int] = {
    val n = list.length / 2
    if (n == ) list
    else {
      val (left, right) = list.splitAt(n)
      merge(sort(left), sort(right))
    }
  }
}

这是一个简单的归并排序实现，使用了 Scala 的模式匹配和递归。您可以将要排序的整数列表传递给 `sort` 函数，它将返回一个已排序的列表。

相关问题

用scala语言写出快速排序

### 回答1：

Scala语言中快速排序的实现可以用以下代码：

def quickSort(array: Array[Int]): Array[Int] = {
if (array.length <= 1) array
else {
val pivot = array(array.length / 2)
Array.concat(
quickSort(array filter (pivot >)),
array filter (pivot ==),
quickSort(array filter (pivot <))
)
}
}

### 回答2：
快速排序是一种常用的排序算法，它采用分治的思想。下面是用Scala语言实现快速排序的代码：

object QuickSort {
  def quickSort(arr: Array[Int]): Array[Int] = {
    if (arr.length <= 1) {
      arr
    } else {
      val pivot = arr(arr.length / 2)
      Array.concat(
        quickSort(arr.filter(_ < pivot)),
        arr.filter(_ == pivot),
        quickSort(arr.filter(_ > pivot))
      )
    }
  }
  
  def main(args: Array[String]): Unit = {
    val arr = Array(7, 2, 9, 1, 6, 5)
    val sortedArr = quickSort(arr)
    println(sortedArr.mkString(" "))
  }
}

在上述代码中，我们定义了一个`QuickSort`对象，并在其中实现了`quickSort`函数。这个函数接收一个整数数组作为参数，并返回排序后的数组。

在函数内部，我们首先判断数组的长度是否小于等于1，如果是的话，直接返回该数组。否则，我们选择数组的中间元素作为枢轴（pivot），然后将数组分成三部分：小于枢轴的元素、等于枢轴的元素以及大于枢轴的元素。

最后，我们使用`Array.concat`函数将这三部分拼接起来，得到最终的排序结果。

在`main`方法中，我们定义了一个测试数组，并将其传入`quickSort`函数进行排序。最后，我们使用`println`函数打印排序后的结果。在这个例子中，输出结果为`1 2 5 6 7 9`。

### 回答3：
快速排序是一种常用的排序算法，使用分治法思想进行排序。在Scala语言中，我们可以通过递归的方式实现快速排序。

以下是使用Scala语言写出的快速排序算法：

def quickSort(arr: Array[Int]): Array[Int] = {
  if (arr.length <= 1) arr // 如果数组长度小于等于1，直接返回
  else {
    val pivot = arr(arr.length / 2) // 基准值选取数组中间的元素
    Array.concat(
      quickSort(arr.filter(_ < pivot)), // 比基准值小的元素递归进行快速排序
      arr.filter(_ == pivot), // 基准值的元素
      quickSort(arr.filter(_ > pivot)) // 比基准值大的元素递归进行快速排序
    )
  }
}

val arr = Array(6, 2, 8, 1, 9)
val sortedArr = quickSort(arr)
println(sortedArr.mkString(", "))

在上述代码中，我们定义了一个名为quickSort的函数，该函数接受一个Int类型的数组作为参数，并返回一个排序后的数组。在函数内部，我们首先检查数组的长度是否小于等于1，如果是，则直接返回该数组。

如果数组长度大于1，我们选择数组中间的元素作为基准值（pivot）。然后通过使用`filter`方法对数组进行筛选，分别得到小于基准值、等于基准值和大于基准值的元素子数组。

接下来，我们对小于基准值和大于基准值的子数组递归调用quickSort函数进行排序，然后通过使用`Array.concat`方法将排序后的子数组和基准值进行合并，最终得到排序后的数组。

最后，我们定义一个示例数组`arr`，并将其传递给`quickSort`函数进行排序。最后，我们通过使用`mkString`方法以逗号分隔打印排序后的数组。

通过以上代码，我们可以使用Scala语言快速实现快速排序算法。

在Scala中，利用List列表实现归并排序。

好的，下面是Scala实现归并排序的示例代码：

def mergeSort[A](list: List[A])(implicit ord: Ordering[A]): List[A] = {
  def merge(left: List[A], right: List[A]): List[A] = (left, right) match {
    case (Nil, right) => right
    case (left, Nil) => left
    case (leftHead :: leftTail, rightHead :: rightTail) =>
      if (ord.lt(leftHead, rightHead)) leftHead :: merge(leftTail, right)
      else rightHead :: merge(left, rightTail)
  }

  val n = list.length / 2
  if (n == 0) list
  else {
    val (left, right) = list.splitAt(n)
    merge(mergeSort(left), mergeSort(right))
  }
}

这段代码定义了一个`mergeSort`函数，它接受一个`List[A]`类型的列表和一个`Ordering[A]`类型的隐式参数，返回一个按照升序排序的新列表。

函数内部定义了一个`merge`函数，它接受两个列表作为参数，返回一个合并后的有序列表。在`merge`函数中，使用模式匹配对列表进行判断，如果其中一个列表为空，直接返回剩下的非空列表；否则，比较两个列表的头部元素，选择较小的一个放到结果列表中，并递归调用`merge`函数处理剩下的元素。

在`mergeSort`函数中，首先计算出列表长度的一半`n`，如果`n`为0，直接返回原列表；否则，将原列表拆分成两个列表`left`和`right`，递归调用`mergeSort`函数对`left`和`right`进行排序，并将排序后的结果传递给`merge`函数进行合并。

你可以使用这段代码进行测试，看看输出结果是否符合预期。希望能帮到你！