有关Scala编程实例
在刚开始学习一门编程语言的时候，总是想去写一些比较大的程序和项目，但是由于基础不扎实，往往欲速则不达。所以，只能一步一步来，通过一些经典的小例子来实践和锻炼，最终不断加深编程的技能，坚持下来，相信慢慢就能够变得熟练。
冒泡排序、选择排序、插入排序的一般写法
这三种排序方法没有太多要说的东西，这里的编程方式和指定式方式没什么差别。
这里之所以使用Array数据，因为Array数组是可变的对象序列，其元素值可以改变，而List类对象的元素是不可变的。
这里的写法不是函数式风格的，其中用到了var可变变量，并且每个函数都是用副作用的，因为这些函数改变了输入数组Array的内容。
def bubbleSort(arr: Array[Int]): Unit = {
for(i <- 0 until arr.length-1; j <- 0 until arr.length-1-i){
if(arr(j) > arr(j+1)){
val tmp = arr(j)
arr(j) = arr(j+1)
arr(j+1) = tmp
}
}
}
def selectSort(arr: Array[Int]): Unit = {
for(i <- 0 until arr.length-1){
var min_ind = i
for(j <- i+1 to arr.length-1) {
if(arr(j) < arr(min_ind)){
min_ind = j
}
}
if(min_ind != i){
val tmp = arr(i)
arr(i) = arr(min_ind)
arr(min_ind) = tmp
}
}
}
def insertSort(arr: Array[Int]): Unit = {
for(i <- 1 until arr.length){
val tmp = arr(i)
var j = i-1
while(j > -1 && arr(j) > tmp){
arr(j+1) = arr(j)
j -= 1
}
arr(j+1) = tmp
}
}
基于模式匹配的插入排序
insertSort函数中采用模式匹配做拆分列表，将分离出来的最左侧的元素插入到按照顺序排列的所在的位置，使用递归调用的方式不断对列表进行拆分。
在指令式的风格中，使用循环的方式，依次取出最左侧的元素，然后插入到从左侧起按照顺序排列的位置。与这种方式有所不同的是，采用递归的函数式的方式，首先递归地对列表进行拆分，然后再按照顺序进行插入。递归的方式结构简洁，但是不容易理解。
def insertSort(xs: List[Int]): List[Int] = xs match {
case List() => List()
case x :: xs1 => insert(x, insertSort(xs1))
}
def insert(x: Int, xs: List[Int]): List[Int] = xs match {
case List() => List(x)
case y :: ys =>
if (x <= y) x :: xs
else y :: insert(x, ys)
}
归并排序
归并排序的工作原理：首先如果列表长度为零或仅有一个元素，它就已经排好序了，因此可以不加改变地返回。长列表可以拆分为两个子列表，每个包含大概一半的原列表元素。每个子列表采用对排列函数的递归调用完成排序，然后再用归并操作把产生的两个排好序的列表合并在一起。
这里先贴出代码再解释：
def merge(a: List[Int], b: List[Int]): List[Int] = (a,b) match {
case (Nil, _) => b
case (_, Nil) => a
case (x::xs, y::ys) =>
if(x <= y) x :: merge(xs, b)
else y :: merge(a, ys)
}
def mergeSort(lst: List[Int]): List[Int] = {
if(lst.length < 2) lst
else{
val (first, second) = lst.splitAt(lst.length/2)
merge(mergeSort(first), mergeSort(second))
}
}
在mergeSort函数中，利用分治策略将子序列进行递归分割，然后再将不断分割的子序列从底向上地合并起来；在merge函数中，通过模式匹配的方式合并两个子序列，在(x::xs, y::ys)对应的模式下，中缀操作符::被当作构造器模式（实际上，存在名为scala.::的类，它可以创建非空列表），这样将列表做拆分，按照元素大小进行排序合并。另外，merge函数使用尾递归的方式来优化性能。
下面是更加函数式风格的写法：
使用函数内函数可以这样写，整体性更佳。对于归并排序的通用实现来说，你可能希望对于待排序列表元素类型不做限制，并同时希望对于用来做元素比较的函数不做限制。这里通过类型参数化来泛化类型，通过使用了柯里化方式，加入比较函数作为参数。
def msort[T](less: (T, T) => Boolean)
(xs: List[T]): List[T] = {
def merge(xs: List[T], ys: List[T]): List[T] =
(xs, ys) match {
case (Nil, _) => ys
case (_, Nil) => xs
case (x :: xs1, y :: ys1) =>
if(less(x, y)) x :: merge(xs1, ys)
else y :: merge(xs, ys1)
}
val n = xs.length / 2
if(n == 0) xs
else {
val (ys, zs) = xs splitAt n
merge(msort(less)(ys), msort(less)(zs))
}
}
}
快速排序
指令性风格的快速排序：
def qsort(xs: Array[Int]): Unit = {
def swap(i: Int, j: Int): Unit = {
val t = xs(i); xs(i) = xs(j); xs(j) = t
}
def sort1(l: Int, r: Int): Unit = {
val pivot = xs((l+r) / 2)
var i = l; var j = r
while(i <= j){
while(xs(i) < pivot) i += 1
while(xs(j) > pivot) j -= 1
if(i <= j){
swap(i, j)
i += 1
j -= 1
}
}
if(l < j) sort1(l, j)
if(j < r) sort1(i, r)
}
sort1(0, xs.length-1)
}
}
函数式风格的快速排序：
def quickSort(xs: Array[Int]): Array[Int] = {
if(xs.length <= 1) xs
else{
val pivot = xs(xs.length / 2)
Array.concat(
quickSort(xs filter (pivot >)),
xs filter (pivot ==),
quickSort(xs filter (pivot <))
)
}
}
更加简洁的快速排序：
def quickSort(lst: List[Int]): List[Int] = {
val p = lst.head
val (before, after) = lst.tail.partition(_ < p)
quickSort(before) ++ (p :: quickSort(after))
}
转载请注明作者Jason Ding及其出处
GitCafe博客主页(http://jasonding1354.gitcafe.io/)
Github博客主页(http://jasonding1354.github.io/)
CSDN博客(http://blog.csdn.net/jasonding1354)
简书主页(http://www.jianshu.com/users/2bd9b48f6ea8/latest_articles)
Google搜索jasonding1354进入我的博客主页
网友评论