乐趣区

关于程序员:算法排序算法

1. 归并排序

go 语言实现 demo_test.go

package demo

import ("testing")

func TestMergeSort(t *testing.T) {arr := []int{1, 9, 1, 4, 0, 8, 7}
    result := Merge(arr)
    t.Log("result=", result)
}

func Merge(arr []int) []int {n := len(arr)   // 求出切片的长度
    m := int(n / 2) // 切片的两头地位
    if n <= 1 {return arr}

    left := Merge(arr[0:m])
    right := Merge(arr[m:n])

    // 合并
    i, j := 0, 0
    result := make([]int, 0)
    for i < m && j < (n-m) {if i < m && j < (n-m) && left[i] <= right[j] {result = append(result, left[i])
            i += 1
        } else if i < m && j < (n-m) && left[i] > right[j] {result = append(result, right[j])
            j += 1
        }
    }
    result = append(result, right[j:(n-m)]...)
    result = append(result, left[i:m]...)
    return result
}
退出移动版