欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Scala排序算法之歸并排序解析

 更新時(shí)間:2023年10月31日 10:45:11   作者:哇哈哈水有點(diǎn)甜  
這篇文章主要介紹了Java排序算法之歸并排序解析,簡介:歸并排序是一種經(jīng)典的排序算法,它采用分治的思想,將待排序的數(shù)組不斷地分割成小的子數(shù)組,然后再將這些子數(shù)組合并成有序的數(shù)組,需要的朋友可以參考下

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)文章

  • Windows7下安裝Scala 2.9.2教程

    Windows7下安裝Scala 2.9.2教程

    這篇文章主要介紹了Windows7下安裝Scala 2.9.2教程,本文給出了Scala的安裝步驟以及在Eclipse IDE安裝Scala的步驟,需要的朋友可以參考下
    2015-03-03
  • Scala基礎(chǔ)簡介及代碼示例

    Scala基礎(chǔ)簡介及代碼示例

    這篇文章主要介紹了Scala基礎(chǔ)簡介及代碼示例,小編覺得挺不錯(cuò)的,這里給大家分享下,供需要的朋友參考。
    2017-10-10
  • 利用Gradle如何構(gòu)建scala多模塊工程的步驟詳解

    利用Gradle如何構(gòu)建scala多模塊工程的步驟詳解

    這篇文章主要給大家介紹了關(guān)于如何利用Gradle構(gòu)建scala多模塊工程的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧。
    2018-04-04
  • Scala排序算法之歸并排序解析

    Scala排序算法之歸并排序解析

    這篇文章主要介紹了Java排序算法之歸并排序解析,簡介:歸并排序是一種經(jīng)典的排序算法,它采用分治的思想,將待排序的數(shù)組不斷地分割成小的子數(shù)組,然后再將這些子數(shù)組合并成有序的數(shù)組,需要的朋友可以參考下
    2023-10-10
  • Scala實(shí)現(xiàn)二分查找的代碼實(shí)例

    Scala實(shí)現(xiàn)二分查找的代碼實(shí)例

    這篇文章主要介紹了Scala實(shí)現(xiàn)二分查找的代碼實(shí)例,找到數(shù)組的中間值,和需要查找的值進(jìn)行對比:如果中間值等于查找值,直接返回中間值下標(biāo);如果中間值大于查找值,則遞歸向左邊查找;如果中間值小于查找值,則遞歸向右邊查找,直到找完所有的元素,需要的朋友可以參考下
    2023-11-11
  • Scala基礎(chǔ)語法總結(jié)

    Scala基礎(chǔ)語法總結(jié)

    這篇文章主要介紹了Scala基礎(chǔ)語法總結(jié),需要的朋友可以參考下
    2023-10-10
  • 淺談Scala的Class、Object和Apply()方法

    淺談Scala的Class、Object和Apply()方法

    下面小編就為大家?guī)硪黄獪\談Scala的Class、Object和Apply()方法。小編覺得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧
    2017-05-05
  • Scala安裝及環(huán)境圖文配置教程

    Scala安裝及環(huán)境圖文配置教程

    這篇文章主要為大家詳細(xì)介紹了Scala安裝及環(huán)境圖文配置教程,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2018-03-03

最新評論