golang之排序算法

下面我们来看下golang实现的排序算法。

快速排序

func QuickSort(arr []int) []int {
	length := len(arr)
	if length <= 1 {
		return arr
	}
	mid := arr[0]
	low, high := make([]int, 0), make([]int, 0)
	for i := 1; i < length; i++ {
		if arr[i] > mid {
			high = append(high, arr[i])
		} else {
			low = append(low, arr[i])
		}
	}

	lowSlice := QuickSort(low)
	highSlice := QuickSort(high)

	return append(append(lowSlice, mid), highSlice...)
}

归并排序

func mergeSort(arr []int) []int {
	length := len(arr)
	if length <= 1 {
		return arr
	}

	mid := length / 2
	left := mergeSort(arr[:mid])
	right := mergeSort(arr[mid:])

	return merge(left, right)
}
func merge(left []int, right []int) []int {
	leftLen := len(left)
	rightLen := len(right)
	i, j := 0, 0
	tmp := make([]int, 0)
	for ;i < leftLen && j < rightLen; {
		if left[i] < right[j] {
			tmp = append(tmp, left[i])
			i++
		} else {
			tmp = append(tmp, right[j])
			j++
		}
	}
	if i < leftLen {
		tmp = append(tmp, left[i:]...)
	} else if j < rightLen {
		tmp = append(tmp, right[j:]...)
	}
	return tmp
}