Scala排序算法之歸并排序解析
Scala實(shí)現(xiàn)歸并排序解析
利用歸并的思想實(shí)現(xiàn)的排序方法,該算法采用經(jīng)典的分治(divide-and-conquer)策略(分治法將問題分(divide)成一些小的問題,然后遞歸求解,而治(conquer)的階段則將分的階段得到的各答案“修補(bǔ)”在一起,即分而治之)
優(yōu)勢:
對于巨大的數(shù)據(jù)集,如果要求Top N這種操作,由于不能把數(shù)據(jù)一次性讀進(jìn)內(nèi)存,快排無法發(fā)揮作用,這時(shí)可以采取歸并的方法,將大的數(shù)據(jù)集分成多個(gè)小的數(shù)據(jù)集,然后分別求Top N,再進(jìn)行歸并,最后從歸并的結(jié)果中求出Top N。
代碼實(shí)現(xiàn)(Scala)
object MergeSort { /** * 測試歸并排序 * @param args */ def main(args: Array[String]): Unit = { var arr = Array(-8, 4, 1, 889, 56, -37) var tmp = new Array[Int](arr.length) mergeSort(arr, 0, arr.length-1, tmp) for (elem <- arr) { println(elem) } } /** * * @param arr 待排序的數(shù)組 * @param left :最初的左邊的下標(biāo):0 * @param right :最初的右邊下標(biāo):length-1 * @param tmp :臨時(shí)數(shù)組,事先開辟好的,大小和arr一樣 */ def mergeSort(arr: Array[Int], left: Int, right: Int, tmp: Array[Int]): Unit = { if (left < right) { //只要left<right,就可以繼續(xù)分,直到將所有元素全部打散成單個(gè) //取數(shù)組中間值下標(biāo) val mid = (left + right) / 2 //對數(shù)組中間元素左側(cè)遞歸切分 mergeSort(arr, left, mid, tmp) //對數(shù)組中間元素右側(cè)遞歸切分 mergeSort(arr, mid + 1, right, tmp) //merge是合并的操作 merge(arr, left, mid, right, tmp) } } def merge(arr: Array[Int], left: Int, mid: Int, right: Int, tmp: Array[Int]) = { var i = left //左邊的開始下標(biāo) var j = mid + 1 //右邊的開始下標(biāo) var t = 0 //臨時(shí)數(shù)組tmp的下標(biāo) while (i <= mid && j <= right) {//同時(shí)滿足這兩個(gè)條件,說明中間元素左右兩側(cè)均還有元素未放到臨時(shí)排序數(shù)組中 if (arr(i) <= arr(j)) { //如果當(dāng)前的左邊的有序列表的值小于當(dāng)前的右邊有序列表的值,把小的值拷貝到tmp數(shù)組中,然后下標(biāo)后移1位 tmp(t) = arr(i) i += 1 t += 1 } else { tmp(t) = arr(j) t += 1 j += 1 } } //不滿足第一個(gè)while條件說明有一側(cè)數(shù)據(jù)已經(jīng)全部拷貝到tmp數(shù)組中了 while (i <= mid) { //如果左邊的有序列表中還有數(shù)據(jù),依次拷貝到tmp數(shù)組中 tmp(t) = arr(i) i += 1 t += 1 } while (j <= right) { //如果右邊的有序列表中還有數(shù)據(jù),依次拷貝到tmp數(shù)組中 tmp(t) = arr(j) j += 1 t += 1 } //將本次的tmp數(shù)組的數(shù)據(jù)拷貝到原數(shù)組arr中 t = 0 //注意這里原數(shù)組下標(biāo)tmpLeft不從0開始,而是從left開始,因?yàn)? var tmpLeft = left while (tmpLeft <= right) { arr(tmpLeft) = tmp(t) tmpLeft += 1 t += 1 } } }
到此這篇關(guān)于Scala排序算法之歸并排序解析的文章就介紹到這了,更多相關(guān)Scala實(shí)現(xiàn)歸并排序解析內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
利用Gradle如何構(gòu)建scala多模塊工程的步驟詳解
這篇文章主要給大家介紹了關(guān)于如何利用Gradle構(gòu)建scala多模塊工程的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧。2018-04-04Scala實(shí)現(xiàn)二分查找的代碼實(shí)例
這篇文章主要介紹了Scala實(shí)現(xiàn)二分查找的代碼實(shí)例,找到數(shù)組的中間值,和需要查找的值進(jìn)行對比:如果中間值等于查找值,直接返回中間值下標(biāo);如果中間值大于查找值,則遞歸向左邊查找;如果中間值小于查找值,則遞歸向右邊查找,直到找完所有的元素,需要的朋友可以參考下2023-11-11淺談Scala的Class、Object和Apply()方法
下面小編就為大家?guī)硪黄獪\談Scala的Class、Object和Apply()方法。小編覺得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧2017-05-05