排序

func MergeSort(arr []int64) []int64 {
	mergeSortC(arr, 0, len(arr)-1)

	return arr
}

func mergeSortC(arr []int64, start, end int) {
	if start >= end {
		return
	}

	q := (start + end) / 2
	mergeSortC(arr, start, q)
	mergeSortC(arr, q+1, end)
	merge(arr, start, q, q+1, end)
}

func merge(arr []int64, leftStart, leftEnd int, rightStart, rightEnd int) {
	var tmp = make([]int64, 0)
	var leftIdx, rightIdx = leftStart, rightStart

	for leftIdx <= leftEnd && rightIdx <= rightEnd {
		if arr[leftIdx] <= arr[rightIdx] {
			tmp = append(tmp, arr[leftIdx])
			leftIdx++
		} else {
			tmp = append(tmp, arr[rightIdx])
			rightIdx++
		}
	}

	// 将子数组剩余部分放入到 tmp 中
	var (
		remainStart = leftIdx
		remainEnd   = leftEnd
	)
	if leftIdx > leftEnd {
		remainStart = rightIdx
		remainEnd = rightEnd
	}
	for remainStart <= remainEnd {
		tmp = append(tmp, arr[remainStart])
		remainStart++
	}

	// 将 tmp 的元素放入 arr 对应位置中
	for idx := 0; idx <= (rightEnd - leftStart); idx++ {
		arr[leftStart+idx] = tmp[idx]
	}
}

func QuickSort(arr []int64) []int64 {
	n := len(arr) - 1
	quickSortC(arr, 0, n)

	return arr
}

func quickSortC(arr []int64, p, r int) {
	if p >= r {
		return
	}

	q := partition(arr, p, r)
	quickSortC(arr, p, q-1)
	quickSortC(arr, q+1, r)

}

func partition(arr []int64, p, r int) int {
	// 我们选择子数组中最后一个元素作为 p 点，循环结束后，将 p 点放到中间，保证左边小于它，右边大于等于它
	pivot := arr[r]
	i := p
	for j := p; j <= r-1; j++ {
		if arr[j] < pivot {
			if i != j {
				tmp := arr[i]
				arr[i] = arr[j]
				arr[j] = tmp
			}
			i++
		}
	}

	tmp := arr[i]
	arr[i] = arr[r]
	arr[r] = tmp

	return i
}