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)) }
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。
相关推荐
-
Scala安装及环境图文配置教程
Window 上安装配置Scala,供大家参考,具体内容如下 1.Java(JDK)环境配置,详见 Java(JDK)环境 2.从 Scala 官网下载安装包:下载地址 3.双击开始一步一步的安装: 4.同意 License: 5.此处可以选择取消"Update system PATH"的设置,随后手动设置环境变量: 6.开始安装吧: 7.安装完成: 8.接着需要设置系统环境变量: 右击[我的电脑]--[属性]--[高级系统设置]--[环境变量],如下图: 在用户变量下新增 SCALA
-
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
随着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中变量的声明与函数定义 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函数式编程过程
深入理解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实现冒泡排序、归并排序和快速排序的示例代码
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语言实现交换排序算法(冒泡,快速排序)的示例代码
目录 前言 一.冒泡排序 1.基本思想 2.优化 3.扩展 二.快速排序 1.基本思想 2.优化 3.代码 前言 查找和排序是数据结构与算法中不可或缺的一环,是前辈们在算法道路上留下的重要且方便的一些技巧,学习这些经典的查找和排序也能让我们更好和更快的解决问题.在这个专栏中我们会学习六大查找和十大排序的算法与思想,而本篇将详细讲解其中的交换排序——冒泡排序和快速排序: 注意:本文中所有排序按照升序排序,降序只需要把逻辑反过来即可! 一.冒泡排序 1.基本思想 对于很多同学来说冒泡排序是再熟悉不过
-
c语言快速排序算法示例代码分享
步骤为:1.从数列中挑出一个元素,称为 "基准"(pivot);2.重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边).在这个分区退出之后,该基准就处于数列的中间位置.这个称为分区(partition)操作.3.递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序.递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了.虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代(iterat
-
Java快速排序与归并排序及基数排序图解示例
目录 一.快速排序 1.基本介绍 2.代码实现 二.归并排序 1.基本介绍 2.代码实现 三.基数排序 1.基本介绍 2.代码实现 一.快速排序 1.基本介绍 以上面的数组为例分析快速排序. 首先要传入三个值,数组arr[ ] ,最左边下标left ,最右边下标 right.然后将根据左右的下标值计算出中间值mid. 我们要做的就是将左边的值大于mid的放到右边,将右边小于mid的值放到左边. 左右两边分别单独循环,左边找到比mid大的数,右边找到比mid小的数. 两边分别找到符合条件的数后,进
-
Python实现希尔排序,归并排序和桶排序的示例代码
目录 1. 前言 2. 希尔排序 2.1 前后切分 2.2 增量切分 3. 归并排序 3.1 分解子问题 3.2 求解子问题 3.3 合并排序 4. 基数排序 5. 总结 1. 前言 本文将介绍希尔排序.归并排序.基数排序(桶排序). 在所有的排序算法中,冒泡.插入.选择属于相类似的排序算法,这类算法的共同点:通过不停地比较,再使用交换逻辑重新确定数据的位置. 希尔.归并.快速排序算法也可归为同一类,它们的共同点都是建立在分治思想之上.把大问题分拆成小问题,解决所有小问题后,再合并每一个小问题的
-
python实现快速排序的示例(二分法思想)
本文介绍了python实现快速排序的示例(二分法思想),分享给大家,具体如下: 实现思路 将所需要的数字存入一个列表中 1.首先,设置将最左侧的那个数设置为基准数,在列表中索引为0 2.然后设置两个移动位(用于比较),分别为最左边和最右边 3.然后最右边那位向左移寻找比基准数小的那一位,最右边那位则从左向右寻找比基准数大的那一位 4.再后,将找到的两位对应的数字替换,继续执行3,直到两个移动位相遇,把基准为替换到相遇的那一位 5.最后,将列表以基准数那一位一分为二切开,左边和右边部分继续执行上述
-
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实现冒泡排序的示例代码
冒泡排序: (Bubble Sorting)基本思想是通过对待排序序列从后向前(从下标较大的元素开始)以此比较相邻元素的排序码,若发现逆序则交换,使排序码较小的元素逐渐从后补移向前部(从下标较大的单元移向单位较小的单元),就像水底的气泡一样逐渐向上冒. 因为排序的过程中,各元素不断的接近自己的位置,如果一趟比较下来没有进行过交换,就说明序列有序,因此要在排序过程中设置一个标志flag判断元素是否进行过交换,从而减少不必要的比较(优化). BubleSort.go package main; im
随机推荐
- win2000/winXP 停止打印的bat
- SVN出现提示org.apache.subversion.javahl.ClientException: Attempted to lock an already-locked dir解决方案
- IOS手势操作(拖动、捏合、旋转、点按、长按、轻扫、自定义)
- 解读ASP.NET 5 & MVC6系列教程(11):Routing路由
- 延时重复执行函数 lLoopRun.js
- 深入PHP empty(),isset(),is_null()的实例测试详解
- 解析阿里云ubuntu12.04环境下配置Apache+PHP+PHPmyadmin+MYsql
- 利用Python破解验证码实例详解
- percona-toolkit对MySQL的复制和监控类操作教程
- Wordpress 忘记密码的处理方法
- JavaScript实现将数组中所有元素连接成一个字符串的方法
- Js中setTimeout()和setInterval() 何时被调用执行的用法
- 漂亮的提示信息(带箭头)
- jquery实现鼠标滑过显示二级下拉菜单效果
- SWFObject 2.1以上版本语法介绍
- 2012世界末日倒计时代码 原来没事虚惊一场
- Java Spring 事务回滚详解
- Firefox下的网页截图插件
- JavaScript数据操作_浅谈原始值和引用值的操作本质
- PHP使用星号隐藏用户名,手机和邮箱的实现方法