menu Chancel's blog
rss_feed
Chancel's blog
秋雨一何碧,山色倚晴空。

Go语言分治算法实践(归并排序与快速排序)

作者:Chancel Yang, 时间:2022 May 25, 阅读:175

1. 问题

分治算法(Divide and conque),指将一个复杂的问题拆分成数个相似的子问题,直到每个子问题都可以简单的直接求解

分治算法是许多高效算法的基础,如归并排序、快速排序、二分搜索法等均用到了分治算法的思想

分治算法在高级语言中的重要体现便是“递归算法”,递归算法是分治法的一个重要思想

2. 求最大值

2.1. 普通算法

给定一个随机数组,从中选出最大与最小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.2. 分治算法

给定一个随机数组,从中选出最大与最小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个步骤

  1. 拆解:将原问题拆解成形式相同的若干个规模较小的子问题
  2. 解决:子问题规模符合直接解决时则直接解决,否则递归拆解
  3. 合并:将各个子问题合并为问题的解

上述例子虽然简单但体现了分治算法的思想

下面以 归并排序算法快速排序算法 为例

看看在排序算法中是如何应用分治算法的思想

3. 数组排序

给定10个随机数字作为数组 arr ,对数组 arr 进行排序

3.1. 归并排序(Merge sort)

归并排序算法的实现如下

  1. 分割:递归数组平均分成2部分
  2. 整合:保持元素顺序并合并所有子序列

归并算法的时间复杂度为$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

归并算法也可用迭代法实现,此处不赘述

3.2. 快速排序算法

快排原理

  1. 挑选:选择一个基准值
  2. 交换:以基准值为准,将大于基准值的元素交换到基准值右边,小于基准值的元素交换到左边
  3. 递归:将基准值左边/右边各视为一个数组继续递归快速排序

快速排序算法是不稳定的排序算法,基于冒泡排序算法改进

时间复杂度

  • 平均时间复杂度:$O(nlogn)$
  • 最坏情况:$O(n^2)$

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

4. 资料引用

Quicksort - Wikipedia

Merge sort - Wikipedia


[[replyMessage== null?"发表评论":"发表评论 @ " + replyMessage.m_author]]

account_circle
email
web_asset
textsms

评论列表([[messageResponse.total]])

还没有可以显示的留言...
[[messageItem.m_author]] [[messageItem.m_author]]
[[messageItem.create_time]]
[[getEnviron(messageItem.m_environ)]]
[[subMessage.m_author]] [[subMessage.m_author]] @ [[subMessage.parent_message.m_author]] [[subMessage.parent_message.m_author]]
[[subMessage.create_time]]
[[getEnviron(messageItem.m_environ)]]
目录