欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

面试算法篇-合并两个有序数组 (快速排序、归并排序)

程序员文章站 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
}