快速排序（填坑法）

快排

具体步骤

• 选择一个基准值，通常选取数组的第一个元素（begin）为基准值，并将其位置设置为坑位，然后从最右端（end）开始寻找符合条件的值填坑
• 右边指针（right）找到比基准值小的，就将其放到坑位上，并将此位置设为新坑
• 从左边指针（left）开始寻找比基准大的数，找到后将其放到坑位，并将其设为新坑
• 当两边指针相遇时，设置为新坑（pipt）将基准放入坑位中，此时就呈现了基准左边小于基准值，基准右边大于基准值
• 然后开始进行【begin，pipt-1】，【pipi+1，end】进行递归

代码示例

func QK(arr []int) {
	if len(arr) < 2 {
		return
	}
	QuickSort(arr, 0, len(arr)-1)
}
func QuickSort(arr []int, left, right int) {
	if left >= right {
		return
	}
	key := arr[left]
	i, j := left, right

	for i < j {
		//从右边找第一个小于基准的元素
		for arr[j] >= key && i < j {
			j--
		}
		//填坑
		if i < j {
			arr[i] = arr[j]
			i++
		}

		//从左边找第一个大于基准的元素
		for arr[i] <= key && i < j {
			i++
		}
		//填坑
		if i < j {
			arr[j] = arr[i]
			j--
		}
	}
	// 将基准元素填坑
	arr[i] = key

	//继续排基准左边和右边的数组
	QuickSort(arr, left, i-1)
	QuickSort(arr, j+1, right)

}