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

布满荆棘的人生 2023-03-13 05:09 5阅读 0赞

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
    }