golang:快速排序以及终极优化

这里使用的是双头并进的快速排序，做法为对于一个待排序列，首先选择一个base，也有人叫做哨兵，或者pivot等等名词。然后将小于base的值放在左边，大于base的值放在右边。然后对放在左边的数字进行快排，对放在右边的数字也进行快排。

golang源码：

func quickSort(nums []int, left, right int)  {
	if left < right {
		mid := partition(nums, left, right)
		quickSort(nums, left, mid-1)
		quickSort(nums, mid + 1, right)
	}
}

// 返回调整完毕之后的pivot的位置，便于之后对两边的数组进行快排
func partition(nums []int, left, right int) int {
	// choose a base num
	pivot := nums[left]
	for left < right {
		for right > left && nums[right] >= pivot {
			right -= 1
		}
		nums[left] = nums[right]
		for left < right && nums[left] <= pivot {
			left += 1
		}
		nums[right] = nums[left]
	}
	//nums[left], nums[index] = nums[index], nums[left]
	nums[left] = pivot
	return left
}

接下来谈到优化，这里有两个基本的优化方案：

1. 基准值的选择，越靠近中位数越好
2. 使用为递归减少递归的层数

对于第一个我们采取三个数去中位数作为基准的方法：

func threeSumMedian(a, b, c int) int {

	if a < b {
		a, b = b, a
	}
	// a  > b

	if c > a {
		return a
	} else {
		if c > b {
			return c
		} else {
			return b
		}
	}
}

那么原来的快速排序中的partition就变成了这样的：

func partition(nums []int, left, right int) int {
	// choose a pivot
	
	// 改变的地方
	pivot := threeSumMedian(nums[left], nums[(left+right)/2], nums[right])
	//pivot := nums[left]
	nums[left], pivot = pivot, nums[left]
	// 改变结束
	
	for left < right {
		for pivot <= nums[right] && left < right {
			right -= 1
		}
		nums[left] = nums[right]

		for nums[left] <= pivot && left < right {
			left += 1
		}
		nums[right] = nums[left]
	}

	nums[left] = pivot
	return left

}

接下来我们对quicksort里面的位置采取尾递归的方式，也就是用迭代来取代递归：

func quickSort(nums []int, left, right int) {
	for left < right {
		mid := partition(nums, left, right)
		quickSort(nums, left, mid-1)
		left = mid + 1
	}
}
// 改变的位置 就是把if改为for
// 然后将第二个quicksort递归改为重新赋值

最终优化完整版如下所示：

func quickSort(nums []int, left, right int) {
	for left < right {
		mid := partition(nums, left, right)
		quickSort(nums, left, mid-1)
		left = mid + 1
	}
}

func partition(nums []int, left, right int) int {
	// choose a pivot

	// 改变的地方
	pivot := threeSumMedian(nums[left], nums[(left+right)/2], nums[right])
	//pivot := nums[left]
	nums[left], pivot = pivot, nums[left]
	// 改变结束

	for left < right {
		for pivot <= nums[right] && left < right {
			right -= 1
		}
		nums[left] = nums[right]

		for nums[left] <= pivot && left < right {
			left += 1
		}
		nums[right] = nums[left]
	}

	nums[left] = pivot
	return left

}

// input 10 20 30 ---> return 20 ; input 10 10 11 --> return 10
func threeSumMedian(a, b, c int) int {

	if a < b {
		a, b = b, a
	}
	// a  > b

	if c > a {
		return a
	} else {
		if c > b {
			return c
		} else {
			return b
		}
	}
}