歸并排序是一種效率比較高的排序算法，但是它額外需要一個(gè)和需要排序的數(shù)組同樣大小的空間溉知。但是在時(shí)間和空間進(jìn)行取舍陨瘩，我們一般會(huì)選擇時(shí)間優(yōu)先。
歸并排序的思想是將一個(gè)數(shù)組分為兩半级乍，然后每個(gè)再分為兩半舌劳，依次繼續(xù)分，直到每個(gè)元素為一個(gè)單獨(dú)的數(shù)組玫荣，然后可以認(rèn)為它們每個(gè)都是有序的甚淡。接下來(lái)就是相鄰的兩個(gè)小數(shù)組合并為一個(gè)較大有序數(shù)組，合并完成之后捅厂，成為每個(gè)具有兩個(gè)元素的有序小數(shù)組贯卦，再進(jìn)行合并，最后整個(gè)序列變?yōu)橐粋€(gè)有序序列焙贷。
這里的難點(diǎn)在于如何將兩個(gè)有序的小數(shù)組合并為一個(gè)有序的較大數(shù)組撵割。這里采用分治的思想來(lái)解決這個(gè)問題。
func merger(arr1 []int, arr2 []int) {
// 存放排序完成的數(shù)組
arr3 := make([]int, len(arr1)+len(arr2))
for i, j, k := 0, 0, 0; k < len(arr3); k++ {
// 如果i越界則說(shuō)明arr1已經(jīng)全部進(jìn)入arr3
// j越界說(shuō)明arr2全部進(jìn)入arr3
// 剩下的操作只需要把剩余一個(gè)數(shù)組的剩余元素放入arr3
if i > len(arr1)-1 {
arr3[k] = arr2[j]
j++
} else if j > len(arr2)-1 {
arr3[k] = arr1[i]
i++
} else if arr1[i] < arr2[j] {
arr3[k] = arr1[i]
i++
} else {
arr3[k] = arr2[j]
j++
}
}
// 顯示結(jié)果
for _, e := range arr3 {
fmt.Println(e)
}
}
上面我們完成了將兩個(gè)有序數(shù)組合并為一個(gè)有序數(shù)組辙芍，那么歸并排序就顯而易見了
func mergeSort(arr []int, l int, r int) {
if l >= r {
return
}
mid := int((l + r) / 2)
mergeSort(arr, l, mid)
mergeSort(arr, mid+1, r)
merge(arr, l, mid, r)
}
func merge(arr []int, l int, mid int, r int) {
aux := make([]int, r-l+1)
copy(aux, arr[l:r+1])
i, j, k := l, mid+1, l
for k <= r {
if i > mid {
arr[k] = aux[j-l]
j++
} else if j > r {
arr[k] = aux[i-l]
i++
} else if aux[i-l] < aux[j-l] {
arr[k] = aux[i-l]
i++
} else {
arr[k] = aux[j-l]
j++
}
k++
}
}
