目录
- 350-两个数组的交集
- 283-移动零
- 1-两数之和
- 25-K 个一组翻转链表
- 581-最短无序连续子数组
- 合并区间
- 螺旋矩阵
- 数组中相加和为0的三元组
- 数组中出现次数超过一半的数字
- 字符串出现次数的TopK问题
- 206-反转链表
- 160-相交链表
- 19-删除链表的倒数第N个节点
- 21-合并两个有序链表
- 31-下一个排列
- 链表K位翻转
- 链表排序-归并算法
- 判断链表中是否有环
- 设计LRU缓存结构
- 两个链表的第一个公共结点
- 两个链表生成相加链表
- 合并N个有序链表
- 链表内指定区间反转
归并排序
访问量:1991
一、简介
思路:主要利用分而治之的策略,把待排序的数组逐渐分解,针对分解后数组进行排序,最终合并排序的多个小数组即可。具体如下图:
二、实现
func Sort(data []int) []int { dataLen := len(data) if dataLen == 0 { return data } if dataLen == 1 { return data } if dataLen == 2 { if data[0] > data[1] { temp := data[0] data[0] = data[1] data[1] = temp } return data } // 拆分 middle := dataLen / 2 leftData := Sort(data[:middle]) rightData := Sort(data[middle:]) // 合并 return Merge(leftData, rightData) } // 合并 func Merge(data1, data2 []int) []int { data1Len := len(data1) data2Len := len(data2) data := make([]int, data1Len+data2Len) i := 0 index1 := 0 index2 := 0 for { if index1 > data1Len && index2 > data2Len { break } if index1 >= data1Len { if index2 >= data2Len { break } data[i] = data2[index2] i++ index2++ continue } else { if index2 >= data2Len || data1[index1] <= data2[index2] { data[i] = data1[index1] i++ index1++ continue } data[i] = data2[index2] i++ index2++ } } return data }
三、性能分析
1、稳定的排序
2、时间复杂度 n * logn
本文为原创文章,请尊重辛勤劳动,如需转载,请保留本文地址
若您感觉本站文章不错,读后有收获,不妨赞助一下?
我要赞助