Go语言实现快速排序快速排序一次快速排序的过程快速排序全过程实现代码总结

快速排序

步骤一：如果要排序数组中下标从 p 到 r 之间的一组数据，选择 p 到 r 之间的任意一个数据作为 pivot（分区点）。步骤二：遍历 p 到 r 之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot 放到中间。经过这一步骤之后，数组 p 到 r 之间的数据就被分成了三个部分，前面 p 到 q-1 之间都是小于 pivot 的，中间是 pivot，后面的 q+1 到 r 之间是大于 pivot 的。步骤三：在分区点pivot左右部分重复步骤一、步骤二。直到数组有序。

一次快速排序的过程

快速排序全过程

实现代码

func QuickSort(array []int) {
	SortDetail(array, 0, len(array)-1)
}

//l,r分别为数组的最左、最右下标
func SortDetail(array []int, l, r int) {
	//递归一定要有截止条件
	if l >= r {
		return
	}
	point := Partition(array, l, r)
	SortDetail(array, l, point-1)
	SortDetail(array, point+1, r)
}

//分区函数
func Partition(array []int, l, r int) int {
	//pivot为分区点，这里选择数组的最后一个元素作为分区点
	point := array[r]
	//i元素为数组最左元素的下标
	i := l
	for j := l; j < r; j++ {
		if array[j] < point {
			array[i], array[j] = array[j], array[i]
			i++
		}
	}
	//上面for循环只是到r-1,这里处理最后一个元素pivot
	array[i], array[r] = array[r], array[i]
	return i
}

func main() {
	array := []int{39, 2, 5, 23, 54, 12, 78, 34, 45, 40}
	QuickSort(array)
	for i, v := range array {
		fmt.Printf("下标为%d的值为%d", i, v)
		fmt.Println()
	}
}

总结

1. 空间复杂度：空间复杂度是O(1), 在上面代码中的Partition分区函数中，考虑到不浪费额外的存储空间，在分区时使用原地交换的方式进行分区
2. 稳定性：快速排序不是稳定的排序方式，在分区函数Partition中，元素位置的交换会导致相同元素的先后顺序改变
3. 时间复杂度：如果选择的分区点不能把数组分区成均衡的两部分，而是极端的不平衡，比如数组基本有序，选择的分区点是最后一个且最大值，快排的时间复杂度会退化成O(n2)，一般情况下，快排的时间复杂度都稳定在O(nlogn)。

最后

以上就是淡然山水为你收集整理的Go语言实现快速排序快速排序一次快速排序的过程快速排序全过程实现代码总结的全部内容，希望文章能够帮你解决Go语言实现快速排序快速排序一次快速排序的过程快速排序全过程实现代码总结所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。