目录

快速排序

快排思想

通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列

就是需要确定一个 pivot支点,然后将小于pivot的放到左边,大于pivot的放到右边,此时pivot就已经排好序了,然后再分别对两别进行递归排序

所以快排主要需要解决下面两个问题:

  • pivot的选择,最好的pivot就是选择当前数组中最中间大小的数
  • 如何把元素放到左边和右边,也就是如何确定pivot放置的位置

复杂度分析

最优时间复杂度: O(nlogn) 最优空间复杂度: O(logn)

pivot每次都平分,计算时间复杂度过程和 归并排序一样计算

空间复杂度主要是递归栈的空间,看递归树的高度,比如50,10,90,30, 70,40,80,60,20 这个序列,递归深度如下,这是一颗平衡二叉树,高度是数组个数的 logn

https://raw.githubusercontent.com/biningo/cdn/master/img/quick.jpg

最差时间复杂度: O(n^2) 最差空间复杂度: O(n)

pivot每次取最大最小值,退化为 冒泡排序 冒泡排序的时间复杂度:

T[n] = n * (n-1) = n^2 + n = O(n^2)

空间复杂度就是树的高度,单边树的高度就是元素的个数,所以空间复杂度为O(n)

pivot支点的选择

支点只要能将两边平均分就是最好的支点,主要有如下几个选法:

  • 选第一个/最后一个
  • 选中间一个
  • 随机选一个
  • 三数取中法: 选 开头、结尾、中间 的数中大小排中间的数

为了便于算法实现,需要取中间某个Pivot时,可以通过交换元素,转换成取第一个(或最后一个)来方便实现

//随机
pivot := rand.Intn(end+1-start) + start

//三数取中
func getMiddle(arr []int, start, end int) int {
	mid := start + (end-start)/2
	if arr[start] > arr[mid] {
		mid, start = start, mid
	}
	if arr[mid] > arr[end] {
		mid, end = end, mid
	}
	return mid
}

//取数组位置中间的数
pivot:=len(arr)/2

移动元素算法

pivot放到合适的位置也有下面几种算法:

  • 遍历法
  • 两端搜索交换法
  • 挖坑法

下面为了方便,直接选取第一个值为pivot,一般其他选取的算法也都是会交换到第一个位置来的

1、遍历法

//3、遍历
func QuickSort_1(arr []int, start, end int) {
	if start >= end {
		return
	}
    //index为pivot最终的位置,最终要满足 [start~index-1] < [index] < [index+1 ~ end]
	index := start
	pivot := start

    //循环过程中,先不移动pivot,满足 [start+1 ~ index] < pivot < [index+1 ~ end]
	for i := start + 1; i <= end; i++ {
		if arr[i] < arr[pivot] {
			index++
			arr[index], arr[i] = arr[i], arr[index]
		}
	}
	arr[index], arr[pivot] = arr[pivot], arr[index]
	pivot = index
	QuickSort_3(arr, start, pivot-1)
	QuickSort_3(arr, pivot+1, end)
}

2、两端搜索交换

//1、两端口遍历
func QuickSort_1(arr []int, start int, end int) {
	if start >= end {
		return
	}
	rand.Seed(time.Now().UnixNano())
	pivot := start

	i, j := start, end
	for i < j {
		//先找右边第一个比pivot小的数 注意顺序 请思考
		for i < j && arr[j] >= arr[pivot] {
			j--
		}
        //找左边第一个比pivot大的数
		for i < j && arr[i] <= arr[pivot] {
			i++
		}
		if i < j {
			arr[i], arr[j] = arr[j], arr[i]
		}
	}
	//移动pivot到正确的位置
	arr[pivot], arr[i] = arr[i], arr[pivot]
	pivot = i
	QuickSort_1(arr, start, pivot-1)
	QuickSort_1(arr, pivot+1, end)
}

3、挖坑法

//挖坑 https://www.bilibili.com/video/BV1Ur4y1w7tv?p=13
func QuickSort_2(arr []int, start, end int) {
	if start >= end {
		return
	}
	pivot := start //选取第一个元素 挖第一个坑
	i, j := start, end
	for i < j {
		for i < j && arr[j] >= arr[pivot] {
			j--
		}
		if i < j {
			arr[i] = arr[j]
		}
		for i < j && arr[i] <= arr[pivot] {
			i++
		}
		if i < j {
			arr[j] = arr[i]
		}
	}
	arr[i] = arr[pivot]
	pivot = i
	QuickSort_1(arr, start, pivot-1)
	QuickSort_1(arr, pivot+1, end)
}

参考

快速排序算法分析与实现

快速排序法为什么一定要从右边开始的原因