Scala实现常用排序算法

下面我将用 Scala 实现几种常用的排序算法，包括冒泡排序、选择排序、插入排序、快速排序和归并排序。这些实现将充分利用 Scala 的函数式编程特性，如不可变数据结构和高阶函数。

object SortingAlgorithms {def main(args: Array[String]): Unit = {val numbers = List(3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5)println(s"原始列表: $numbers")println(s"冒泡排序: ${bubbleSort(numbers)}")println(s"选择排序: ${selectionSort(numbers)}")println(s"插入排序: ${insertionSort(numbers)}")println(s"快速排序: ${quickSort(numbers)}")println(s"归并排序: ${mergeSort(numbers)}")}// 冒泡排序def bubbleSort(list: List[Int]): List[Int] = {def bubblePass(lst: List[Int]): List[Int] = lst match {case a :: b :: rest if a > b => b :: bubblePass(a :: rest)case a :: b :: rest => a :: bubblePass(b :: rest)case single => single}def sortHelper(lst: List[Int], n: Int): List[Int] = if (n == 0) lst else sortHelper(bubblePass(lst), n - 1)sortHelper(list, list.length)}// 选择排序def selectionSort(list: List[Int]): List[Int] = list match {case Nil => Nilcase _ =>val min = list.minval (before, after) = list.span(_ != min)min :: selectionSort(before ++ after.tail)}// 插入排序def insertionSort(list: List[Int]): List[Int] = {def insert(element: Int, sortedList: List[Int]): List[Int] = sortedList match {case Nil => List(element)case head :: tail if element <= head => element :: sortedListcase head :: tail => head :: insert(element, tail)}list.foldLeft(List.empty[Int])((acc, elem) => insert(elem, acc))}// 快速排序def quickSort(list: List[Int]): List[Int] = list match {case Nil => Nilcase pivot :: tail =>val (less, greater) = tail.partition(_ <= pivot)quickSort(less) ++ (pivot :: quickSort(greater))}// 归并排序def mergeSort(list: List[Int]): List[Int] = {def merge(left: List[Int], right: List[Int]): List[Int] = (left, right) match {case (Nil, _) => rightcase (_, Nil) => leftcase (lHead :: lTail, rHead :: rTail) =>if (lHead <= rHead) lHead :: merge(lTail, right)else rHead :: merge(left, rTail)}val mid = list.length / 2if (mid == 0) listelse {val (left, right) = list.splitAt(mid)merge(mergeSort(left), mergeSort(right))}}
}

这些排序算法的实现特点如下：

1. 冒泡排序：通过多次遍历列表，每次比较相邻元素并交换位置，将最大元素"冒泡"到末尾。实现中使用了辅助函数bubblePass处理单次遍历。

2. 选择排序：每次找出列表中的最小元素，将其放在已排序部分的末尾，然后对剩余元素重复这一过程。

3. 插入排序：构建有序列表，对于每个新元素，将其插入到有序列表的适当位置。这里使用了foldLeft函数式风格实现。

4. 快速排序：选择一个基准元素，将列表分为小于等于基准和大于基准的两部分，然后递归排序这两部分并合并结果。使用partition方法使代码更加简洁。

5. 归并排序：采用分治法，将列表分为两半，分别排序后再合并两个有序列表。merge函数负责合并两个有序列表。

所有实现都使用了 Scala 的不可变List数据结构，符合函数式编程的思想，避免了副作用。每种算法都有其适用场景，例如快速排序通常性能较好，而归并排序则是稳定排序。