跟我一起学“仓颉”算法-分治算法
目录
一、分治
二、合并排序
三、小结
一、分治
分治：分而治之。
满足分治算法的条件：
- 原问题可被分解成若干个规模较小的子问题；
- 子问题相互独立；
- 子问题的解可以合并为原问题的解。
二、合并排序
合并排序就是将待排序的大数组分解成待排序的小数组，然后把每个小数组进行排序，最终将排好序的小数组合并成有序的大数组，时间复杂度：O(nlogn)。
package Algorithm func mergeSort(array: Array<Int64>, low: Int64, high: Int64): Array<Int64> { if (low < high) { let mid = low + (high - low)/ 2 mergeSort(array, low, mid) mergeSort(array, mid + 1, high) var newArray = Array<Int64>(high - low + 1, repeat: 0) var i = low var j = mid + 1 var k = 0 while (i <= mid && j <= high) { if (array[i] <= array[j]) { newArray[k] = array[i] i++ k++ } else { newArray[k] = array[j] j++ k++ } } while (i <= mid) { newArray[k] = array[i] i++ k++ } while (j <= high) { newArray[k] = array[j] j++ k++ } return newArray } return array } main(): Int64 { let array = [4, 9, 15, 24, 30, 2, 6, 18, 20] // let array = [1,3,2] println(mergeSort(array, 0, array.size - 1)) return 0 }三、小结
本章为大家详细的介绍了仓颉数据结构与算法中分治算法的内容，下一章，为大家带来分治算法练习题的内容。最后，创作不易，如果大家觉得我的文章对学习仓颉数据结构与算法有帮助的话，就动动小手，点个免费的赞吧！收到的赞越多，我的创作动力也会越大哦，谢谢大家🌹🌹🌹！！！