basic algorithm

快排

核心思想：取一个数作为基准，比这个数小的放在左边，大的放在右边，然后左边重复，右边重复。

基准元素，一般来说选取有几种方法

• 取第一个元素
• 取最后一个元素
• 取第中间位置元素

实现方式：一般递归+双指针

伪代码

1：首先取序列第一个元素为基准元素pivot=R[low]。i=low,j=high。
2：从后向前扫描，找小于等于pivot的数，如果找到，R[i]与R[j]交换，i++。
3：从前往后扫描，找大于pivot的数，如果找到，R[i]与R[j]交换，j--。 
4: 重复2~3，直到i=j,返回该位置mid=i,该位置正好为pivot元素。 完成一趟排序后，以mid为界，将序列分为两部分，左序列都比pivot小，有序列都比pivot大，然后再分别对这两个子序列进行快速排序。

时间复杂度（0nlogn）

参考：

https://zhuanlan.zhihu.com/p/63227573