有關(guān)Scala編程實例
在剛開始學(xué)習(xí)一門編程語言的時候币厕，總是想去寫一些比較大的程序和項目，但是由于基礎(chǔ)不扎實埂蕊，往往欲速則不達(dá)往弓。所以疏唾，只能一步一步來，通過一些經(jīng)典的小例子來實踐和鍛煉函似，最終不斷加深編程的技能槐脏，堅持下來，相信慢慢就能夠變得熟練撇寞。
冒泡排序顿天、選擇排序、插入排序的一般寫法
這三種排序方法沒有太多要說的東西蔑担，這里的編程方式和指定式方式?jīng)]什么差別牌废。
這里之所以使用Array數(shù)據(jù)，因為Array數(shù)組是可變的對象序列啤握，其元素值可以改變鸟缕，而List類對象的元素是不可變的。
這里的寫法不是函數(shù)式風(fēng)格的排抬，其中用到了var可變變量懂从，并且每個函數(shù)都是用副作用的，因為這些函數(shù)改變了輸入數(shù)組Array的內(nèi)容畜埋。
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函數(shù)中采用模式匹配做拆分列表莫绣，將分離出來的最左側(cè)的元素插入到按照順序排列的所在的位置，使用遞歸調(diào)用的方式不斷對列表進(jìn)行拆分悠鞍。
在指令式的風(fēng)格中对室，使用循環(huán)的方式，依次取出最左側(cè)的元素咖祭，然后插入到從左側(cè)起按照順序排列的位置掩宜。與這種方式有所不同的是，采用遞歸的函數(shù)式的方式么翰，首先遞歸地對列表進(jìn)行拆分牺汤，然后再按照順序進(jìn)行插入。遞歸的方式結(jié)構(gòu)簡潔浩嫌，但是不容易理解檐迟。
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)
}
歸并排序
歸并排序的工作原理：首先如果列表長度為零或僅有一個元素，它就已經(jīng)排好序了码耐，因此可以不加改變地返回追迟。長列表可以拆分為兩個子列表，每個包含大概一半的原列表元素骚腥。每個子列表采用對排列函數(shù)的遞歸調(diào)用完成排序敦间，然后再用歸并操作把產(chǎn)生的兩個排好序的列表合并在一起。
這里先貼出代碼再解釋：
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函數(shù)中，利用分治策略將子序列進(jìn)行遞歸分割廓块，然后再將不斷分割的子序列從底向上地合并起來厢绝；在merge函數(shù)中，通過模式匹配的方式合并兩個子序列带猴，在(x::xs, y::ys)對應(yīng)的模式下昔汉，中綴操作符::被當(dāng)作構(gòu)造器模式（實際上，存在名為scala.::的類浓利，它可以創(chuàng)建非空列表）挤庇，這樣將列表做拆分，按照元素大小進(jìn)行排序合并贷掖。另外嫡秕，merge函數(shù)使用尾遞歸的方式來優(yōu)化性能。
下面是更加函數(shù)式風(fēng)格的寫法：
使用函數(shù)內(nèi)函數(shù)可以這樣寫苹威，整體性更佳昆咽。對于歸并排序的通用實現(xiàn)來說，你可能希望對于待排序列表元素類型不做限制牙甫，并同時希望對于用來做元素比較的函數(shù)不做限制掷酗。這里通過類型參數(shù)化來泛化類型，通過使用了柯里化方式窟哺，加入比較函數(shù)作為參數(shù)泻轰。
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))
}
}
}
快速排序
指令性風(fēng)格的快速排序：
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)
}
}
函數(shù)式風(fēng)格的快速排序：
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))
}
轉(zhuǎn)載請注明作者Jason Ding及其出處
GitCafe博客主頁(http://jasonding1354.gitcafe.io/)
Github博客主頁(http://jasonding1354.github.io/)
CSDN博客(http://blog.csdn.net/jasonding1354)
簡書主頁(http://www.reibang.com/users/2bd9b48f6ea8/latest_articles)
Google搜索jasonding1354進(jìn)入我的博客主頁
