1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71
| package advanced_sort
import ( "algos/模板/排序/util" "fmt" "sort" )
func MergeSort(nums []int) { mergeSort(nums, 0, len(nums)-1) }
func mergeSort(nums []int, l, r int) { if l == r { return }
mid := l + (r-l)>>1 mergeSort(nums, l, mid) mergeSort(nums, mid+1, r) merge(nums, l, mid, r)
}
func merge(nums []int, l, mid, r int) { i, j := l, mid+1 cur := 0 help := make([]int, r-l+1) for i <= mid && j <= r { if nums[i] < nums[j] { help[cur], cur, i = nums[i], cur+1, i+1 } else { help[cur], cur, j = nums[j], cur+1, j+1 } }
for i <= mid { help[cur], cur, i = nums[i], cur+1, i+1 } for j <= r { help[cur], cur, j = nums[j], cur+1, j+1 }
for i := 0; i < len(help); i++ { nums[l+i] = help[i] } }
func main() { nums := util.GenerateRandomNums(0, 100, 30) fmt.Println(nums) temp := make([]int, 30) copy(temp, nums) sort.Ints(temp) MergeSort(nums) fmt.Println(temp) fmt.Println(nums) }
|