做网站销售这几天你有什么想法,贵阳手机网站建设,网线制作注意事项,如何注册公司企业邮箱大家好#xff0c;我是蓝胖子#xff0c;我一直相信编程是一门实践性的技术#xff0c;其中算法也不例外#xff0c;初学者可能往往对它可望而不可及#xff0c;觉得很难#xff0c;学了又忘#xff0c;忘其实是由于没有真正搞懂算法的应用场景#xff0c;所以我准备出… 大家好我是蓝胖子我一直相信编程是一门实践性的技术其中算法也不例外初学者可能往往对它可望而不可及觉得很难学了又忘忘其实是由于没有真正搞懂算法的应用场景所以我准备出一个系列囊括我们在日常开发中常用的算法并结合实际的应用场景真正的感受算法的魅力。 代码已经上传github
https://github.com/HobbyBear/codelearning/tree/master/mergesort算法原理
每每实现算法的时候我总是倾向于用文字将算法的逻辑描述出来当你能清晰的描述算法逻辑的时候实现起来就是水到渠成的事情。
所以我们接下来首先看下归并排序的算法逻辑。归并排序的时间复杂度是nO(lg n)它要求每次 将数组一分为二,被分割的数组又一分为二直至不能被分割最后由底向上进行两两合并。你可以看到假设数组长度是n整个过程一共有lg n层每一层需要对n个元素进行合并所以时间复杂度是nO(lg n)。如下图所示: 合并的过程是将合并的两个有序数组的元素变成一个有序数组的过程我们把这个过程称为merge于是我们将 归并排序的详细步骤总结为如下的步骤
1将数组一分为二,形成左右子数组。
2对左子数组进行归并排序。
3对右子数组进行归并排序。
4对左右子数组进行merge。
详细的merge操作我们可以在O(n)时间复杂度内完成详细步骤可以总结如下:
1用i表示左子数组当前遍历的元素j表示右边子数组当前遍历的元素。
2创建一个新数组用于保存排好序的元素开始遍历左右子数组如果左右子数组都没有遍历完则比较各自当前遍历元素的大小将小的元素复制到新数组然后移动小元素所在数组当前遍历的指针指向下一个遍历元素。
3如果其中一个数组遍历完成则只需要将没有遍历完的那个数组剩下元素全部复制到新数组即可。
实现
了解了上述详细步骤后我们可以很容易的用递归实现上述归并排序逻辑。
// 将数组[l...r]一分为二分别对左右数组进行排序然后对排序好的数组进行归并
func mergesort(arr []int, l, r int) { if l r { return } mid : (l r) / 2 mergesort(arr, l, mid) mergesort(arr, mid1, r) merge(arr, l, mid, r)
}merge 部分代码如下 写算法逻辑的时候一定要注意边界条件比如我这里定义的是闭区间那么下面的逻辑都是按闭区间去写的。 // [l...mid] [mid1...r]
func merge(arr []int, l, mid, r int) { arr1 : arr[l : mid1] arr2 : arr[mid1 : r1] newArr : make([]int, r-l1) i : 0 // 当前遍历元素 j : 0 k : 0 for i len(arr1) j len(arr2) { if arr1[i] arr2[j] { newArr[k] arr2[j] j k continue } newArr[k] arr1[i] k i } if i len(arr1) { copy(newArr[k:], arr2[j:]) } if j len(arr2) { copy(newArr[k:], arr1[i:]) } copy(arr[l:], newArr)
}应用 求解逆序对的数量
关于归并排序的一个应用我这里用leetcode一个题举例这个题是leetcode 的剑指 Offer 51题求解逆序对。
剑指 Offer 51. 数组中的逆序对
困难
1.1K
相关企业
在数组中的两个数字如果前面一个数字大于后面的数字则这两个数字组成一个逆序对。输入一个数组求出这个数组中的逆序对的总数。 示例 1:
输入: [7,5,6,4]
输出: 5 限制 0 数组长度 50000这道题可以采用归并排序的思想在merge时得到逆序对的数量如下, merge时的两个数组是有序的且归并排序的左右数组的相对顺序是不变的当右边数组合并到左边数组时如果左边的数组元素大则说左边数组当前遍历的元素和其以后的元素都可以和右边的数组构成一个逆序对。
所以我们可以在merge的代码逻辑中添加一段累计逆序对的逻辑如下:
func mergeCopy(arr []int, l, mid, r int, cnt *int) { arr1 : arr[l : mid1] arr2 : arr[mid1 : r1] newArr : make([]int, r-l1) i : 0 // 当前遍历元素 j : 0 k : 0 for i len(arr1) j len(arr2) { if arr1[i] arr2[j] { newArr[k] arr2[j] // 新增cnt 变量用于保存逆序对的数量*cnt len(arr1) - i j k continue } newArr[k] arr1[i] k i } if i len(arr1) { copy(newArr[k:], arr2[j:]) } if j len(arr2) { copy(newArr[k:], arr1[i:]) } copy(arr[l:], newArr)
}
