温习mergesort归并排序
2023-07-05 本文已影响0人
robertzhai
image.png
package main
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 将给定数组排序
* @param arr int整型一维数组 待排序的数组
* @return int整型一维数组
*/
func MySort(arr []int) []int {
// write code here
mergeSort(arr, 0, len(arr)-1)
return arr
}
// 归并排序 O(nlogn)
// 是一种分而治之的算法，其思想是将一个列表分解为几个子列表，
// 直到每个子列表由一个元素组成，然后将这些子列表合并为排序后的列表。
// 先把数组从中间分成前后两部分，然后对前后两部分分别排序，
// 再将排好序的两部分合并在一起，这样整个数组就都有序了。
func mergeSort(arr []int, left, right int) {
if left < right {
mid := left + (right-left)>>1
mergeSort(arr, left, mid)
mergeSort(arr, mid+1, right)
merge(arr, left, mid, right) //通过比较2个部分的元素来合并2个部分
}
}
// 合并2个有序数组
func merge(arr []int, left, mid, right int) {
tmp := make([]int, right-left+1)
i, j,k := left, mid+1,0
for i <= mid && j <= right {
if arr[i] <= arr[j] {
tmp[k] = arr[i]
i++
} else {
tmp[k] = arr[j]
j++
}
k++
}
for i <= mid {
tmp[k] = arr[i]
k++
i++
}
for j <= right {
tmp[k] = arr[j]
k++
j++
}
copy(arr[left:right+1], tmp)
}
