跟我一起学“仓颉”算法-分治算法

目录一、分治二、合并排序三、小结一、分治分治分而治之。满足分治算法的条件原问题可被分解成若干个规模较小的子问题子问题相互独立子问题的解可以合并为原问题的解。二、合并排序合并排序就是将待排序的大数组分解成待排序的小数组然后把每个小数组进行排序最终将排好序的小数组合并成有序的大数组时间复杂度O(nlogn)。package Algorithm func mergeSort(array: ArrayInt64, low: Int64, high: Int64): ArrayInt64 { if (low high) { let mid low (high - low)/ 2 mergeSort(array, low, mid) mergeSort(array, mid 1, high) var newArray ArrayInt64(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 }三、小结本章为大家详细的介绍了仓颉数据结构与算法中分治算法的内容下一章为大家带来分治算法练习题的内容。最后创作不易如果大家觉得我的文章对学习仓颉数据结构与算法有帮助的话就动动小手点个免费的赞吧收到的赞越多我的创作动力也会越大哦谢谢大家