Scala实现冒泡排序、归并排序和快速排序的示例代码

1、冒泡排序

def sort(list: List[Int]): List[Int] = list match {
  case List() => List()
  case head :: tail => compute(head, sort(tail))
 }

 def compute(data: Int, dataSet: List[Int]): List[Int] = dataSet match {
  case List() => List(data)
  case head :: tail => if (data <= head) data :: dataSet else head :: compute(data, tail)
 }

def main(args: Array[String]) {
  val list = List(3, 12, 43, 23, 7, 1, 2, 0)
  println(sort(list))
 }

2、归并排序

def mergedSort[T](less: (T, T) => Boolean)(list: List[T]): List[T] = {

  def merged(xList: List[T], yList: List[T]): List[T] = {
   (xList, yList) match {
    case (Nil, _) => yList
    case (_, Nil) => xList
    case (x :: xTail, y :: yTail) => {
     if (less(x, y)) x :: merged(xTail, yList)
     else
      y :: merged(xList, yTail)
    }
   }
  }

  val n = list.length / 2
  if (n == 0) list
  else {
   val (x, y) = list splitAt n
   merged(mergedSort(less)(x), mergedSort(less)(y))
  }
 }

def main(args: Array[String]) {
  val list = List(3, 12, 43, 23, 7, 1, 2, 0)
  println(mergedSort((x: Int, y: Int) => x < y)(list))
 }

3、快速排序

 def quickSort(list: List[Int]): List[Int] = {
  list match {
   case Nil => Nil
   case List() => List()
   case head :: tail =>
    val (left, right) = tail.partition(_ < head)
    quickSort(left) ::: head :: quickSort(right)
  }
 }

def main(args: Array[String]) {
  val list = List(3, 12, 43, 23, 7, 1, 2, 0)
  println(quickSort(list))
 }

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

  • 深入理解Scala函数式编程过程

    深入理解Scala函数式编程过程 我们马上开始一段变态的过程 如果要求立方和,可以这么做 35 * 35 * 35 68 * 68 * 68 没毛病,抽象一点儿,写个函数: def cube(n: Int) = n * n * n cube(35) cube(68) 省事儿了,如果求1到10的立方和,OK,写个递归 def cube(n: Int) = n * n * n def sumCube(a: Int, b: Int): Int = if (a > b) 0 else cube(a) +

  • Scala基础简介及代码示例

    一.主要内容 Scala中变量的声明与函数定义 Scala中的控制结构 Scala中的数据类型 1:变量声明与函数定义 变量声明:val 和 var ,两者的区别是val声明的变量是不可变的,而var声明的变量可变 带返回值 scala> def max(x:Int,y:Int):Int = { | if(x>y) x | else y | } max: (x: Int, y: Int)Int scala> max(1,2) res5: Int = 2 不带返回值 scala> d

  • Scala解析Json字符串的实例详解

    Scala解析Json字符串的实例详解 1. 添加相应依赖 Json解析工具使用的 json-smart,曾经对比过Java的fastjson.gson.Scala的json4s.lift-json.其中 json-smart 解析速度是最快的. <dependency> <groupId>net.minidev</groupId> <artifactId>json-smart</artifactId> <version>2.3<

  • 浅析Java和Scala中的Future

    浅析Java和Scala中的Future

    随着CPU的核数的增加,异步编程模型在并发领域中的得到了越来越多的应用,由于Scala是一门函数式语言,天然的支持异步编程模型,今天主要来看一下Java和Scala中的Futrue,带你走入异步编程的大门. Future 很多同学可能会有疑问,Futrue跟异步编程有什么关系?从Future的表面意思是未来,一个Future对象可以看出一个将来得到的结果,这就和异步执行的概念很像,你只管自己去执行,只要将最终的结果传达给我就行,线程不必一直暂停等待结果,可以在具体异步任务执行的时候去执行其他操作

  • Scala小程序详解及实例代码

    Scala小程序详解 1. 交互式模式 在命令行窗口中,输入Scala命令: xiaosi@Qunar:~$ scala Welcome to Scala 2.11.8 (Java HotSpot(TM) 64-Bit Server VM, Java 1.8.0_91). Type in expressions for evaluation. Or try :help. scala> 第一个小程序: xiaosi@Qunar:~$ scala Welcome to Scala 2.11.8 (

  • Scala安装及环境图文配置教程

    Scala安装及环境图文配置教程

    Window 上安装配置Scala,供大家参考,具体内容如下 1.Java(JDK)环境配置,详见 Java(JDK)环境 2.从 Scala 官网下载安装包:下载地址 3.双击开始一步一步的安装: 4.同意 License: 5.此处可以选择取消"Update system PATH"的设置,随后手动设置环境变量: 6.开始安装吧: 7.安装完成: 8.接着需要设置系统环境变量: 右击[我的电脑]--[属性]--[高级系统设置]--[环境变量],如下图: 在用户变量下新增 SCALA

  • Scala实现冒泡排序、归并排序和快速排序的示例代码

    1.冒泡排序 def sort(list: List[Int]): List[Int] = list match { case List() => List() case head :: tail => compute(head, sort(tail)) } def compute(data: Int, dataSet: List[Int]): List[Int] = dataSet match { case List() => List(data) case head :: tail

  • C语言实现交换排序算法(冒泡,快速排序)的示例代码

    C语言实现交换排序算法(冒泡,快速排序)的示例代码

    目录 前言 一.冒泡排序 1.基本思想 2.优化 3.扩展 二.快速排序 1.基本思想 2.优化 3.代码 前言 查找和排序是数据结构与算法中不可或缺的一环,是前辈们在算法道路上留下的重要且方便的一些技巧,学习这些经典的查找和排序也能让我们更好和更快的解决问题.在这个专栏中我们会学习六大查找和十大排序的算法与思想,而本篇将详细讲解其中的交换排序——冒泡排序和快速排序: 注意:本文中所有排序按照升序排序,降序只需要把逻辑反过来即可! 一.冒泡排序 1.基本思想 对于很多同学来说冒泡排序是再熟悉不过

  • c语言快速排序算法示例代码分享

    步骤为:1.从数列中挑出一个元素,称为 "基准"(pivot);2.重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边).在这个分区退出之后,该基准就处于数列的中间位置.这个称为分区(partition)操作.3.递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序.递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了.虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代(iterat

  • Java快速排序与归并排序及基数排序图解示例

    Java快速排序与归并排序及基数排序图解示例

    目录 一.快速排序 1.基本介绍 2.代码实现 二.归并排序 1.基本介绍 2.代码实现 三.基数排序 1.基本介绍 2.代码实现 一.快速排序 1.基本介绍 以上面的数组为例分析快速排序. 首先要传入三个值,数组arr[ ] ,最左边下标left ,最右边下标 right.然后将根据左右的下标值计算出中间值mid. 我们要做的就是将左边的值大于mid的放到右边,将右边小于mid的值放到左边. 左右两边分别单独循环,左边找到比mid大的数,右边找到比mid小的数. 两边分别找到符合条件的数后,进

  • Python实现希尔排序,归并排序和桶排序的示例代码

    Python实现希尔排序,归并排序和桶排序的示例代码

    目录 1. 前言 2. 希尔排序 2.1 前后切分 2.2 增量切分 3. 归并排序 3.1 分解子问题 3.2 求解子问题 3.3 合并排序 4. 基数排序 5. 总结 1. 前言 本文将介绍希尔排序.归并排序.基数排序(桶排序). 在所有的排序算法中,冒泡.插入.选择属于相类似的排序算法,这类算法的共同点:通过不停地比较,再使用交换逻辑重新确定数据的位置. 希尔.归并.快速排序算法也可归为同一类,它们的共同点都是建立在分治思想之上.把大问题分拆成小问题,解决所有小问题后,再合并每一个小问题的

  • python实现快速排序的示例(二分法思想)

    python实现快速排序的示例(二分法思想)

    本文介绍了python实现快速排序的示例(二分法思想),分享给大家,具体如下: 实现思路 将所需要的数字存入一个列表中 1.首先,设置将最左侧的那个数设置为基准数,在列表中索引为0 2.然后设置两个移动位(用于比较),分别为最左边和最右边 3.然后最右边那位向左移寻找比基准数小的那一位,最右边那位则从左向右寻找比基准数大的那一位 4.再后,将找到的两位对应的数字替换,继续执行3,直到两个移动位相遇,把基准为替换到相遇的那一位 5.最后,将列表以基准数那一位一分为二切开,左边和右边部分继续执行上述

  • C语言植物大战数据结构快速排序图文示例

    C语言植物大战数据结构快速排序图文示例

    目录 快速排序 一.经典1962年Hoare法 1.单趟排序 2.递归左半区间和右半区间 3.代码实现 二.填坑法(了解) 1.单趟思路 2.代码实现 三.双指针法(最佳方法) 1.单趟排序 2.具体思路 3.代码递归图 4.代码实现 四.三数取中优化(最终方案) 1.三数取中 2.代码实现(最终代码) 五.时间复杂度(重点) 1.最好情况下 2.最坏情况下 3.空间复杂度 六.非递归写法 1.栈模拟递归快排 2.队列实现快排 浅浅总结下 “田家少闲月,五月人倍忙”“夜来南风起,小麦覆陇黄” C

  • c++实现对输入数组进行快速排序的示例(推荐)

    废话不多说,直接上代码 #include "stdafx.h" #include <iostream> #include <string> #include <vector> using namespace std; void quickSort(vector<int> &a, int, int); void swap(int &a, int&b); vector<string> split(strin

  • c++实现二路归并排序的示例代码

    二路归并排序 基本思想 二路归并排序就是将两个有序子表归并成一个有序表.首先我们得有一个算法用于归并:两个有序表放在同一数组的相邻位置上,arr[left]到arr[center-1]为第一个有序表,arr[center]到arr[right]是第二个有序表.每次从两端中取出一个进行比较,小的先放在一个temp数组,最后将比较剩下的直接放到temp中去,最后将temp又复制回arr.这是"治". 所谓"分",就是递归地将前半部分和后半部分的数据各自归并排序即可. 算

  • go实现冒泡排序的示例代码

    go实现冒泡排序的示例代码

    冒泡排序: (Bubble Sorting)基本思想是通过对待排序序列从后向前(从下标较大的元素开始)以此比较相邻元素的排序码,若发现逆序则交换,使排序码较小的元素逐渐从后补移向前部(从下标较大的单元移向单位较小的单元),就像水底的气泡一样逐渐向上冒. 因为排序的过程中,各元素不断的接近自己的位置,如果一趟比较下来没有进行过交换,就说明序列有序,因此要在排序过程中设置一个标志flag判断元素是否进行过交换,从而减少不必要的比较(优化). BubleSort.go package main; im

随机推荐