归并排序的时间复杂度为:O(nlogn)
func HeapSort(data []int) []int {
len := len(data)
if len <=1 {
return data
}
//将待排序的数组划分为左右2部分,递归的进行
mid :=len/2
left :=data[:mid]
right :=data[mid:]
left= HeapSort(left)
right= HeapSort(right)
//对划分后的两部分进行排序
return Sort(left,right)
}
func Sort(left []int,right []int) []int {
llen :=len(left)
rlen :=len(right)
var tmp []int
i,j:=0,0
for {
//如果left先遍历结束,则将right剩余部分追加到tmp中
if i >=llen{
tmp =append(tmp,right[j:]...)
break
}
//如果right部分先遍历结束,则将left剩余部分追加到tmp中
if j >=rlen{
tmp =append(tmp,left[i:]...)
break
}
//比较left和right将较小的元素存入tmp
if left[i] < right[j] {
tmp =append(tmp,left[i])
i++
}else{
tmp =append(tmp,right[j])
j++
}
}
return tmp
}
//测试:
func main() {
arr :=[]int{0,1,5,2,3,8,0,4,9,2}
r:=HeapSort(arr)
fmt.Println(r)
}
输出:[0 0 1 2 2 3 4 5 8 9]
有疑问加站长微信联系(非本文作者)