目录
1.什么是快速排序
2.核心思想
3.代码实现
4.性能分析
1.什么是快速排序
快速排序（简称 快排），计算机科学词汇，使用领域 Pascal，C++ 等语言，是对基本排序算法的升级。快排发明之后，也变成了一种常用的数组排序方式，应用于各类高频的算法题中，是我们必须掌握的一种排序算法。
2.核心思想
快排通过多次比较和交换来实现排序，下面我们来模拟一下这个过程。比如：要对数组 12,49,30,3,49,5,17,2,11,49,22,49 进行排序
首先，用指针对数组的数和分界值进行比较，然后：
当一趟排序以后，我们发现：分界值 12 已经处于数组的中间位置。而分界值左边的数小于分界值，右边的数大于等于分界值。
这样，每次排序都固定好一个中间数，而接下来要做的，就是对中间数的左右区间再次进行同样的排序，最终让整个数组都变成有序的。
下面，我们用视频来模拟快排的全过程：
3. 代码实现
快排算法的实现有很多种，在此，为了和视频保持一致，我们给出了同一种算法；其余的可以下来再学习，一般情况下，熟悉这一种就能覆盖大部分算法题了。
结合上述的排序流程和视频，我们用 Go 语言实现快排算法：
func QUickSort(a []nums, left, right int) {
// 特殊情况处理
if left >= right {
return
}
// 获取分界值的下标，此时左边都小于该分界值，右边都大于或等于该分界值
key := partition(a, left, right)
// 对左边进行排序
QuickSort(a, left, key-1)
// 对右边进行排序
QUickSort(a, key+1, right)
}
// 一趟排序，获取分界值的下标
func partition(a []nums, left, right int) int {
// 分界值为第一个元素,idx为第2个元素
key, idx := nums[left], left+1
for j:=left+1; j<=right; j++ {
if nums[j] < key {
// 交换，idx+1
strs[idx], strs[j] = strs[j], strs[idx]
idx++
}
}
nums[idx-1], nums[left] = nums[left], nums[idx-1]
return idx-1
}4.性能分析
快速排序的一趟排序是从左到右遍历整个数组，因此一趟排序的时间复杂度为 O(n)；所以，整个快排的时间复杂度取决于我们排序的趟数。
理想情况是，每次划分的中间数正好将数组平分，即两边的元素几乎一样多。这种情况下，我们对其递归排序时，只需要
最坏的情况是，每次选的中间数都是当前序列的最小或者最大元素，这使得递归次数和数组长度一样多。因此，最坏情况下的时间复杂度为
为了改善最坏情况下的时间性能，我们可以采用三者值取中：即从 nums[left], nums[right] 和 nums[(left+right)/2] 中选取中间值来作为一趟排序的分界值。
或者，选取一个随机数作为分界值，以避免该序列取到的分界值是数组中最大或者最小的。
因此，快排的平均复杂度为 O(nlogn)，该算法被认为是目前最好的一种内部排序方法。
