面试算法篇-合并两个有序数组 (快速排序、归并排序)
程序员文章站
2024-03-16 12:59:04
...
package main
import "fmt"
func main() {
arr := []int{2,1,4,3, 5, 6,7, 9}
quickSort(arr, 0, len(arr))
fmt.Println(mergeSort(arr, 0, len(arr)))
dealSortOrderArrs()
}
/**
合并两个有序数组
*/
func dealSortOrderArrs() {
arr1 := []int{1, 3, 5, 7}
arr2 := []int{100, 104, 106, 108}
fmt.Println(merge(arr1, arr2))
}
/**
归并排序
*/
func mergeSort(arr []int, l, r int) []int {
if len(arr) <= 1 {
return arr
}
mid := (l+r)/2
L := mergeSort(arr[:mid-l], l, mid)
R := mergeSort(arr[mid-l:], mid, r)
//合并两个有序数组
return merge(L, R)
}
/**
归并排序,合并两个有序数组
*/
func merge(lArr, rArr []int) []int {
tmp := make([]int, 0)
i := 0
lLen := len(lArr)
j := 0
rLen := len(rArr)
for true {
if i < lLen && j < rLen {
if lArr[i] < rArr[j] {
tmp = append(tmp, lArr[i])
i++
} else {
tmp = append(tmp, rArr[j])
j++
}
}
if i < lLen && j == rLen {
tmp = append(tmp, lArr[i])
i++
}
if i == lLen && j < rLen {
tmp = append(tmp, rArr[j])
j++
}
if i == lLen && j == rLen {
break
}
}
return tmp
}
/**
快速排序
*/
func quickSort(arr []int, l, r int) {
if r-l <= 1 {
return
}
mid := find(arr, l, r)
quickSort(arr, l, mid)
quickSort(arr, mid+1, r)
return
}
/**
快速排序,找到中间位置
*/
func find(arr []int, l, r int) int {
tmp := arr[l]
p := l
i, j := l, r-1
for i<=j {
//倒序找到第一个比tmp小的
for j>=p && arr[j] >= tmp {
j--
}
if j >= p {
arr[p] = arr[j]
p = j
}
//顺序找到第一个比tmp大的
for i<=p && arr[i] <= tmp {
i++
}
if i <= p {
arr[p] = arr[i]
p = i
}
}
arr[p] = tmp
return p
}
上一篇: LeetCode刷题:20. Valid Parentheses
下一篇: 每日算法系列