golang實現(xiàn)歸并排序

歸并排序的操作步驟如下:

  1. 首先將數(shù)組一份為二,分別為左數(shù)組和右數(shù)組
  2. 若左數(shù)組的長度大于1,那么對左數(shù)組實施歸并排序
  3. 若右數(shù)組的長度大于1, 那么對右數(shù)組實施歸并排序
  4. 將左右數(shù)組進(jìn)行合并

代碼如下:

package main

import (
    "fmt"
)

// mergerSort
func mergerSort(arr []int, a, b int) {
    if b-a <= 1 {
        return
    }

    c := (a + b) / 2
    mergerSort(arr, a, c)
    mergerSort(arr, c, b)

    arrLeft := make([]int, c-a)
    arrRight := make([]int, b-c)
    copy(arrLeft, arr[a:c])
    copy(arrRight, arr[c:b])
    i := 0
    j := 0
    for k := a; k < b; k++ {
        if i >= c-a {
            arr[k] = arrRight[j]
            j++
        } else if j >= b-c {
            arr[k] = arrLeft[i]
            i++
        } else if arrLeft[i] < arrRight[j] {
            arr[k] = arrLeft[i]
            i++
        } else {
            arr[k] = arrRight[j]
            j++
        }
    }
}

func main() {
    // 測試代碼
    arr := []int{9, 8, 7, 6, 5, 1, 2, 3, 4, 0}
    fmt.Println(arr)
    mergerSort(arr, 0, len(arr))
    fmt.Println(arr)
}
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成,瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明:文章內(nèi)容(如有圖片或視頻亦包括在內(nèi))由作者上傳并發(fā)布,文章內(nèi)容僅代表作者本人觀點(diǎn),簡書系信息發(fā)布平臺,僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 一些概念 數(shù)據(jù)結(jié)構(gòu)就是研究數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)以及它們之間相互關(guān)系,并對這種結(jié)構(gòu)定義相應(yīng)的運(yùn)算,而且確保經(jīng)過這...
    Winterfell_Z閱讀 6,612評論 0 13
  • 1 初級排序算法 排序算法關(guān)注的主要是重新排列數(shù)組元素,其中每個元素都有一個主鍵。排序算法是將所有元素主鍵按某種方...
    深度沉迷學(xué)習(xí)閱讀 1,608評論 0 1
  • 一、 單項選擇題(共71題) 對n個元素的序列進(jìn)行冒泡排序時,最少的比較次數(shù)是( )。A. n ...
    貝影閱讀 9,432評論 0 10
  • 概述 排序有內(nèi)部排序和外部排序,內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進(jìn)行排序,而外部排序是因排序的數(shù)據(jù)很大,一次不能容納全部...
    蟻前閱讀 5,305評論 0 52
  • 1.插入排序—直接插入排序(Straight Insertion Sort) 基本思想: 將一個記錄插入到已排序好...
    依依玖玥閱讀 1,356評論 0 2

友情鏈接更多精彩內(nèi)容