# 快速排序 * **介绍** * 复杂度O(n log(n)) * 思路:取一个元素p(第一个元素),使元素p`归位`; 列表被p分成两部分,左边都比p小,右边都比p大; 递归完成排序. * 过程: `锁定`从右边找第一个数值p,先从右边找比p小的数,把右边的值写到左边空位上;然后从左边找比p大的数,把左边的值写到右边空位上; 依次取完所有的数值. * 关键字: * `归位`获取中数的下标 * 归位是指将列表通过两端对调比一个值的方式,将数组分成关于每个数对称的两部分和一个中间值。 * 目的:使目标具有一致性和折半处理的格式。 * 递归 * 存在问题 * 最坏情况存在(`优化`:加入随机替换) * 极端情况下排序效率低 * 快速排序 `>` 归并排序 `>` 堆排序 * **原理** > * **代码** ```go /** Quick 实现快速排序 O(n * log(n)) a : 被排序数组 返回:排序完毕数组 */ func Quick(slice []int, left, right int) []int { if left < right { mid := partition(slice, left, right) // 获取归位中值 Quick(slice, left, mid-1) // 操作 中值 左边数组 Quick(slice, mid+1, right) // 操作 中值 右边数组 } return slice } /** partition 归位函数,获取一个关于某值对称的数组和中间值 */ func partition(slice []int, left, right int) int { tmp := slice[left] // 获取左侧第一个数 for left < right { // 进行逐个实现归位操作,将列表形成一个对称列表 // 左边比 tmp 大的数,调至右边 for left < right && slice[right] >= tmp { right-- } slice[left] = slice[right] // 右边比 tmp 小的数,调至左边 for left < right && slice[left] <= tmp { left++ } slice[right] = slice[left] } slice[left] = tmp return left } ``` * **过程** ![快速](.\img\快速排序.gif) ![快速排序示例图](.\img\快速排序示例图.png)