Scala函数式编程实现排序算法

　　记得《Function Thinking》这本书中提到，现在的编程范式有两类，一类是“命令式编程”，另一类是“函数式编程”，现在我们最常使用的许多语言像c、c++、java都是命令式的，但其中c++和java也都有一些函数式的类库，可见函数式特性还是受一些程序员的青睐的。还有一些纯函数式的语言如 clojure、haskell则完全是纯函数式的。像python、scala则是混合型的，包含两种范式，给程序员提供了巨大的灵活性，使解决问题的方式更多，可谓是程序员的一大利器。
现在就以scala语言的"pattern matching"来实现一些经典的排序算法，来展示一下函数式编程思维方式上带给我们的惊喜和享受。

1. 冒泡排序

原理：

通过相邻元素比较交换的方式，将最大的元素依次移动到列表中未排好序部分的尾部，重复操作，直到列表中未排好序的部分为空，从而使整个列表有序

scala实现思路：

新建一冒泡函数bubble(unSorteds: List[A]): A，实现一趟冒泡功能，即从输入列表中冒泡出一个最大元素A
给bubble函数添加两个参数remains: List[A], accOrdereds: List[A],添加后函数如下：bubble(unSorteds: List[A],remains: List[A], accOrdereds: List[A]): A
其中remains用于记录每次冒泡后去掉冒出去的元素后剩余元素列表，
accOrdereds用于累积每趟冒泡冒出来的元素，然后将返回值A改为List[A],即返回累积排好序的列表。
函数bubble使用“模式匹配”匹配为排序的列表，分两种情况
列表中至少有两种元素的情况
列表中只剩余一个元素
这种情况下，当剩余元素列表remains为空时，说明整个排序完成。否则继续递归bubble

具体scala代码如下

object BubbleSort {

  /**

    * @param list 待排序列表

    * @tparam A 列表元素类型

    * @return

    */

  def bubbleSort[A <% Ordered[A]](list: List[A]): List[A] = {

    /**

      * @param unSorteds 每一趟冒泡时待排序列表

      * @param remains  已遍历且未冒出的元素列表

      * @param accOrdereds 已冒出的元素组成的有序列表(是累积的)

      * @return 每一趟冒泡后排好序的列表

      */

    @tailrec def bubble(unSorteds: List[A], remains: List[A], accOrdereds: List[A]): List[A] = unSorteds match {

      case h1 :: h2 :: t =>

        if (h1 > h2) bubble(h1 :: t, h2 :: remains, accOrdereds)

        else bubble(h2 :: t, h1 :: remains, accOrdereds)

      case h1 :: Nil =>

        if (remains.isEmpty)

          return h1 :: accOrdereds

        else bubble(remains, Nil,h1 :: accOrdereds)

    }

    bubble(list, Nil, Nil)

  }

  def main(args: Array[String]): Unit = {

    val list = List(1,13,7,5,8,9,20,43,11,8)

    println(bubbleSort(list))

  }

}

2. 快速排序

原理：

使用分治思想，将数列用选好的基准点划分为两个子序列（也就是将比基准点小的元素放左边，比基准点大的元素放右边），递归对子序列使用此方法进行此操作，递归到最底部时，数列的大小是零或一，也就是已排好序。

使用scala的实现思路:

利用scala的模式匹配对序列进行匹配，分两种情况：

序列为空
为空时返回一个空的List()
序列由head和tail组成，head不为空，这时候以head为基准点将序列划分为left和right两个子序列，然后然后对left和right进行同样操作并将结果quickSort(left)和quickSort(right)与基准元素head连接起来，如此递归操作，直到所有子序列都为空，便已排好序。

scala代码实现：

object QuickSort extends App {

  /**

    * 快速排序

    *

    * @param list 待排序列表

    * @tparam A 列表元素类型

    * @return

    */

  def quickSort[A <% Ordered[A]](list: List[A]): List[A] = list match {

      case Nil => List()

      case head :: tail =>

        val (left, right) = tail.partition(_ < head)

        quickSort(left) ::: head :: quickSort(right)

    }

  val list = List(1, 13, 7, 5, 8, 9, 20, 43, 11, 8)

  println(quickSort(list))

}

3. 插入排序

原理：

通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入，直到将所有未排序数据都插入到已排序序列中，排序便完成

scala实现思路:

新建一个insert函数实现将一个元素插入到已排序序列的功能，函数签名如下 def insert(a: A, accOrdereds: List[A]): List[A]，其中accOrdereds为已经排序序列，且是累积的，即每次insert时传入的都是当前最新的已排序序列。此函数实现思路也是使用模式匹配来实现。
这种情况下
新建一sort函数，函数签名如下：
def sort(unSorteds: List[A], accOrdereds: List[A]): List[A]
其中unSorteds是以模式匹配的方式匹配头和尾，将头元素使用insert函数插入到累积的已排序的序列。然后再使用sort进行下一轮插入。如此递归执行，直到为排序序列unSorteds为空，返回累积已经排好序的序列

注意
scala中List的头(head)是List中第一个元素，List的尾(tail)是去掉头元素(head)后的List

scala代码实现:

object InsertionSort extends App {

  /**

    * @param list 待排列表

    * @tparam A 列表元素类型

    * @return

    */

  def insertionSort[A <% Ordered[A]](list: List[A]): List[A] = {

    /**

      * @param unSorteds 待排列表

      * @param accOrdereds 累积有序列表

      * @return 有序列表

      */

    @tailrec def sort(unSorteds: List[A], accOrdereds: List[A]): List[A] = unSorteds match {

      case ha :: ta => sort(ta, insert(ha, accOrdereds))

      case Nil => accOrdereds

    }

    /**

      * @param a 待插入元素

      * @param accOrdereds 累积有序列表

      * @return

      */

    def insert(a: A, accOrdereds: List[A]): List[A] = accOrdereds match {

        case h :: t if (a > h) => h :: insert(a, t)

        case _ => a :: accOrdereds

      }

    sort(list, Nil)

  }

  val list = List(1,13,7,5,8,9,20,43,11,8)

  println(insertionSort(list).mkString(","))

}

4. 归并排序

原理

使用分治思想，将序列划分为若干个只有一个元素的子序列，重复进行merge排序操作，将子序列两两合并，直到最后只剩下一个子序列，这个子序列就是已排好的序列

scala实现思路:

创建一个merge函数用于合并两个排好序的子序列
def merge(as: List[A], bs: List[A]): List[A]
实现方式通过内建一个loop函数，实现对两个序列的遍历和排序，loop函数签名如下：
def loop(cs: List[A], ds: List[A], accSorteds: List[A]): List[A]
cs和ds是两个已排序序列，accSorteds是累积排序序列，cs和ds合并过程中产生的新的有序列序列
新建一个划分序列并将划分序列合并排序的函数：
splitIn2AndSort(as: List[A]): List[A]

scala代码实现

object MergeSort extends App {

  def mergeSort[A <% Ordered[A]](list: List[A]): List[A] = {

    /**

      * @param p 待排序的包含两个列表的元组

      * @return

      */

    def sort(p: (List[A], List[A])): List[A] = {

      p match {

        case (Nil, Nil) => Nil

        case (a :: Nil, Nil) => a :: Nil

        case (Nil, a :: Nil) => a :: Nil

        case (as, bs) => merge(splitIn2AndSort(as), splitIn2AndSort(bs))

      }

    }

    /**

      * 将给定列表划分为两个列表，并归并排序返回一个有序列表

      * @param as 待划分列表

      * @return

      */

    def splitIn2AndSort(as: List[A]): List[A] = sort(splitIn2(as))

    /**

      * 合并两个有序列表

      * @param as 有序列表

      * @param bs 有序列表

      * @return 合并后的有序列表

      */

    def merge(as: List[A], bs: List[A]): List[A] = {

      def loop(cs: List[A], ds: List[A], accSorteds: List[A]): List[A] = (cs, ds) match {

        case (Nil, Nil) => accSorteds

        case (hc :: tc, hd :: td) =>

          if (hc < hd)

            loop(tc, ds, hc :: accSorteds)

          else

            loop(td, cs, hd :: accSorteds)

        case (hc :: tc, Nil) => loop(tc, Nil, hc :: accSorteds)

        case (Nil, hd :: td) => loop(Nil, td, hd :: accSorteds)

      }

      loop(as, bs, Nil).reverse

    }

    def splitIn2(as: List[A]): (List[A], List[A]) = {

      val mid = as.length / 2

      (as.slice(0, mid), as.slice(mid, as.length))

    }

    splitIn2AndSort(list)

  }

  val list = List(1, 13, 7, 5, 8, 9, 20, 43, 11, 8)

  println(mergeSort(list).mkString(","))

}

5. 选择排序

原理

从原序列中依次移出符合条件(最大或最小)的元素，放入到有序序列中，直到原序列吴待排序元素

scala实现思路：

新建一函数：
def select(remains: List[A], sorteds: List[A], accSorteds: List[A]): List[A]
实现从剩余的未排序序列remains中选出符合条件的元素，将它追加到已排序序列sorteds和累积已排序序列accSorteds中
新建函数：
def sort(remains: List[A], accSorteds: List[A]): List[A]
用来执行一趟选择排序过程，将排序结果累积在accSorteds中，当remains为空时，排序结束，返回accSorteds

scala代码实现：

object SelectionSort extends App {

  def selectionSort[A <% Ordered[A]](list: List[A]): List[A] = {

    /**

      * @param unSorteds 未排序列表

      * @param accSorteds 累积最终的有序列表

      * @return

      */

    def sort(unSorteds: List[A], accSorteds: List[A]): List[A] =

      unSorteds match {

        case h :: t => select(unSorteds, Nil, accSorteds)

        case Nil => accSorteds

      }

    /**

      *

      * @param unSorteds  未排序列表

      * @param sorteds    选择出的元素组成的有序列表

      * @param accSorteds 累积最终的有序列表

      * @return

      */

    @tailrec def select(unSorteds: List[A], sorteds: List[A], accSorteds: List[A]): List[A] =

      unSorteds match {

        case h1 :: h2 :: t =>

          if (h1 < h2)

            select(h2 :: t, h1 :: sorteds, accSorteds)

          else

            select(h1 :: t, h2 :: sorteds, accSorteds)

        case h :: Nil => sort(sorteds, h :: accSorteds)

        case Nil => sort(sorteds, accSorteds)

      }

    sort(list, Nil)

  }

  val list = List(1, 13, 7, 5, 8, 9, 20, 43, 11, 8)

  println(selectionSort(list))

}

以上五种排序算均采用scala函数式方式实现，实现过程多采用递归思维和模式匹配，这也是函数式编程通常使用的方式。

巴特西

Scala函数式编程实现排序算法

1. 冒泡排序

原理：

scala实现思路：

具体scala代码如下

2. 快速排序

原理：

使用scala的实现思路:

scala代码实现：

3. 插入排序

原理：

scala实现思路:

scala代码实现:

4. 归并排序

原理

scala实现思路:

scala代码实现

5. 选择排序

原理

scala实现思路：

scala代码实现：

最新文章

热门文章