E4b9a6's blog
有善始者实繁，能克终者盖寡。
作者：E4b9a6， 创建：2020-06-13， 字数：6483， 已阅：42， 最后更新：2020-06-13
这篇文章更新于 1622 天前，文中部分信息可能失效，请自行甄别无效内容。
分治算法（Divide and conque），指将一个复杂的问题拆分成数个相似的子问题，直到每个子问题都可以简单的直接求解
分治算法是许多高效算法的基础，如归并排序、快速排序、二分搜索法等均用到了分治算法的思想
分治算法在高级语言中的重要体现便是“递归算法”，递归算法是分治法的一个重要思想
给定一个随机数组，从中选出最大与最小2个值
采用最简单的方法，遍历循环就可以得出最大值与最小值
用GO语言实现如下
package main
import (
"fmt"
"math/rand"
)
func main() {
var length int = 100
var random []int
for i := 0; i < length; i++ {
random = append(random, rand.Intn(length))
}
fmt.Println("Array length: ", length)
var minNumber int = random[0]
var maxNumber int = random[0]
for i := 1; i < len(random); i++ {
if random[i] > maxNumber {
maxNumber = random[i]
}
if random[i] < minNumber {
minNumber = random[i]
}
}
fmt.Printf("Max number:%v\nMin number:%v\n", maxNumber, minNumber)
}
其打印如下
Array length: 100
Max number:99
Min number:0
普通算法是最常规求解的方案
给定一个随机数组，从中选出最大与最小2个值
我们采用分治算法来处理
用GO语言实现如下
package main
import (
"fmt"
"math/rand"
)
func GetMaxByArray(array []int, left int, right int) int {
// 空列表表示出错
if len(array) == 0 {
return -1
}
// 下标相撞则直接判断大小
if right-left <= 0 {
if array[left] >= array[right] {
return array[left]
}
return array[right]
}
var middle = int((right-left)/2) + left
var maxLeft = GetMaxByArray(array, left, middle)
var maxRight = GetMaxByArray(array, middle+1, right)
if maxLeft >= maxRight {
return maxLeft
}
return maxRight
}
func GetMinByArray(array []int, left int, right int) int {
// 空列表表示出错
if len(array) == 0 {
return -1
}
// 下标相撞则直接判断大小
if right-left <= 0 {
if array[left] >= array[right] {
return array[right]
}
return array[left]
}
var middle = int((right-left)/2) + left
var maxLeft = GetMinByArray(array, left, middle)
var maxRight = GetMinByArray(array, middle+1, right)
if maxLeft >= maxRight {
return maxRight
}
return maxLeft
}
func main() {
var length int = 100
var random []int
for i := 0; i < length; i++ {
random = append(random, rand.Intn(length))
}
fmt.Println("Array length:", length)
var maxNumber = GetMaxByArray(random, 0, len(random)-1)
var minNumber = GetMinByArray(random, 0, len(random)-1)
fmt.Printf("Max number:%v\nMin number:%v\n", maxNumber, minNumber)
}
输出如下
Array length: 100
Max number:99
Min number:0
分治算法将长度为100的数组拆分成2个50的数组，再将2个50的数组分别拆成2个25的数组
如此往复递归直到数组长度为2时便可直接比较大小，可见并没有减少问题规模
这里可以看出分治算法实现的3个步骤
上述例子虽然简单但体现了分治算法的思想
下面以 归并排序算法 和 快速排序算法 为例
看看在排序算法中是如何应用分治算法的思想
给定10个随机数字作为数组 arr ，对数组 arr 进行排序
归并排序算法的实现如下
归并算法的时间复杂度为$O（nlogn）$，归并算法排序是稳定的排序算法
排序算法的稳定性：指在排序之后依旧保持原数组中的索引大小关系，如[2,3,1,4,5,3]在排序之后[1,2,3,3,4,5]，其中2个数字“3”数组索引分别为1，5，再排序之后索引大小关系依旧成立
GO语言递归版本实现如下
package main
import (
"crypto/rand"
"fmt"
"math/big"
"time"
)
func Merge(arr []int) []int {
var arr_len = len(arr)
// 将数组分为2部分，对左边部分再进行分组，直到数组长度不大于2
var left_arr = arr[:arr_len/2]
var left_arr_len = len(left_arr)
if left_arr_len >= 2 {
left_arr = Merge(left_arr)
}
// 将数组分为2部分，对右边部分再进行分组，直到数组长度不大于2
var right_arr = arr[arr_len/2:]
var right_arr_len = len(right_arr)
if right_arr_len >= 2 {
right_arr = Merge(right_arr)
}
// 对数组进行排序
var left_index int = 0
var right_index int = 0
var sort_arr = make([]int, arr_len)
for i := 0; i < arr_len; i++ {
if right_index == right_arr_len {
sort_arr[i] = left_arr[left_index]
left_index++
continue
}
if left_index == left_arr_len {
sort_arr[i] = right_arr[right_index]
right_index++
continue
}
if left_arr[left_index] <= right_arr[right_index] {
sort_arr[i] = left_arr[left_index]
left_index++
continue
}
if left_arr[left_index] > right_arr[right_index] {
sort_arr[i] = right_arr[right_index]
right_index++
continue
}
}
return sort_arr
}
func main() {
var length int = 10
var randoms []int
for i := 0; i < length; i++ {
// 产生真随机数（性能较差）
n, _ := rand.Int(rand.Reader, big.NewInt(int64(length)))
randoms = append(randoms, int(n.Int64()))
}
fmt.Println("Source array: ", randoms)
var start = time.Now()
var sortRandoms = Merge(randoms)
var elapsed = time.Since(start)
fmt.Println("Sort array: ", sortRandoms)
fmt.Println("Total time: ", elapsed)
}
运行后输出如下
Source array: [5 5 4 3 7 1 0 8 7 8]
Sort array: [0 1 3 4 5 5 7 7 8 8]
Total time: 7.291µs
归并算法也可用迭代法实现，此处不赘述
快排原理
快速排序算法是不稳定的排序算法，基于冒泡排序算法改进
时间复杂度
GO语言实现如下
package main
import (
"crypto/rand"
"fmt"
"math/big"
"time"
)
func QuickSort(array []int, left int, right int) {
if len(array) <= 1 || left >= right {
return
}
// 对数组进行基准（pivot）排序
var mid = Partition(array, left, right)
QuickSort(array, left, mid)
QuickSort(array, mid+1, right)
}
func Partition(array []int, left int, right int) int {
// 取pivot的值为数组最后一个元素
var pivotIndex int = right
// 从左往右遍历数组寻找大于pivot值的元素A，从右往左寻找小于pivot值的元素B，交换元素A与B的位置，直到rightIndex与leftIndex相等
// 遍历结束后，rightIndex（leftIndex）下标数组左边元素均小于pivot值，右边均大于pivot值
var rightIndex int = right - 1
for leftIndex := left; leftIndex < rightIndex; leftIndex++ {
if array[leftIndex] > array[pivotIndex] {
for ; rightIndex > leftIndex; rightIndex-- {
if array[rightIndex] < array[pivotIndex] {
var temp int = array[rightIndex]
array[rightIndex] = array[leftIndex]
array[leftIndex] = temp
break
}
}
}
}
// 因pivot值为数组最后一个元素，若pivot值小于数组下标rightIndex（leftIndex），则交换彼此元素位置
if array[rightIndex] > array[pivotIndex] {
var temp int = array[rightIndex]
array[rightIndex] = array[pivotIndex]
array[pivotIndex] = temp
}
return rightIndex
}
func main() {
var length int = 10
var randoms []int
for i := 0; i < length; i++ {
// 产生真随机数（性能较差）
n, _ := rand.Int(rand.Reader, big.NewInt(int64(length)))
randoms = append(randoms, int(n.Int64()))
}
fmt.Println("Source array: ", randoms)
var start = time.Now()
var elapsed = time.Since(start)
QuickSort(randoms, 0, len(randoms)-1)
fmt.Println("Sort array: ", randoms)
fmt.Println("Total time: ", elapsed)
}
运行输出如下
Source array: [8 4 6 5 3 5 8 4 9 1]
Sort array: [1 3 4 4 5 5 6 8 8 9]
Total time: 220ns