快速排序
目录
快排思想
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
就是需要确定一个 pivot支点，然后将小于pivot的放到左边，大于pivot的放到右边，此时pivot就已经排好序了，然后再分别对两别进行递归排序
所以快排主要需要解决下面两个问题:
pivot的选择，最好的pivot就是选择当前数组中最中间大小的数- 如何把元素放到左边和右边，也就是如何确定
pivot放置的位置
复杂度分析
最优时间复杂度:
O(nlogn)最优空间复杂度:O(logn)
pivot每次都平分，计算时间复杂度过程和 归并排序一样计算
空间复杂度主要是递归栈的空间，看递归树的高度，比如50,10,90,30, 70,40,80,60,20 这个序列，递归深度如下，这是一颗平衡二叉树，高度是数组个数的 logn倍
最差时间复杂度:
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)
}