经典算法，快速排序
主要有一下几个问题要考虑：
1、参照点如何选择
2、交换条件
3、递归终止条件
快速排序（Quicksort）是对归并排序算法的优化，继承了归并排序的优点，同样应用了分治思想。快速排序并不是最好的，它的”快“是建立在综合考虑的基础上，需要根据不同情况选择不同的排序方法，其主要应用在数据有一定规模时。快速排序也是不稳定排序方法。
参照点选择
通常做法是从首尾选择一点作为参照点，将区间分为两部分。但是这样选择有一定弊端，例如数组本身就是有序数组[1,2,3,4,5,6,7,8,9]，或者有序部分占比大，就不能体现快排的优势了。有些文章中说排序之前先对数组打乱，但是这样做本身就会消耗时间，而且打乱结果是未知的，不是明智的做法。还有些文章中说要用随机函数选参照点，但是随机函数本身也是耗时的，所以也不是最好的选择。
如果我们选参照点的时候分别从区间两端和中间选三个值并取三者的中间值作为分割点这样会不会更合理一些呢。操作的时候我们先将这三个点进行从小到大排序这样选完参照点后区间最开始点和最后也已经完成了排序，进行排序只需要从区间开始第二个点和区间倒数第二个点开始了，这样选点的同时也进行了一次排序。（这种选参照点的方式意味着区间内最少有三个点所以选择之前要做一个约束）
所以参照点的选择一定程度上会影响排序效率。
交换条件
移动指针的时候一侧指针停止移动的条件也会影响排序效率，例如数组内均为同一个值[6,6,6,6,6,6,6,6]，或者只有少数不同的值，如果设置停止条件为大于则左侧指针会停在区间右侧，二右侧指针都没有机会移动，这也不能体现出快速排序的优势了，不论参照点怎么选都会有相同的时间复杂度。如果我们设置条件区间左边指针往右移动直到第一个大于等于参照点的位置停下，然后移动右边指针往左移动直到第一个小于等于参照点的位置，这样的话对于数组[6,6,6,6,6,6,6,6]每次左右指针都会交替移动直到区间中心，时间复杂度会有明显下降。当左右指针都停止的时候就要进行交换了，此时需要判断两个指针的位置关系，如果指针出现了交叉则不能进行交换也意味着区间排序的结束。交换后我们需要将指针的值向各自前进方向移动一次，否则如果两个指针所指的值相同下次进入循环和上次出循环的区间状态并没有发生变化就会导致死循环。
递归终止条件
递归的终止是很重要的，不然可能会导致不可预期的结果。递归终止主要判断指针交叉情况，有交叉就结束。有些文章（视频）中指出，当数据量较小的时候可能排序效率不及因为递归有出栈和入栈等一系列操作，这些操作也是耗时的，此时其效率可能不如插入排序或选择排序。所以可以设置一个阈值当区间小于阈值长度的时候调用其他排序方法，本文为了完成递归没有调用其他排序方法，而是将阈值设置为2，然后对满足阈值的区间进行简单的比较和交换，然后终止递归。
python实现如下：
class QuickSort:
_sortlst=[]
_yuzhi=2
def _swap(self,x1,x2):
tmp=self._sortlst[x1]
self._sortlst[x1] =self._sortlst[x2]
self._sortlst[x2] = tmp
#print(self._sortlst[x2], self._sortlst[x1], '交换后：',self._sortlst)
def _Get_mediom(self,st,ed):
c=(ed+st)//2
if self._sortlst[st]>self._sortlst:
self._swap(st,c)
if self._sortlst[ed]<self._sortlst[st]:
self._swap(ed,st)
if self._sortlst[ed]<self._sortlst:
self._swap(ed,c)
#print('中值点index：',c,',值',self._sortlst)
return c
def _sort(self,st,ed):
if ed-st <= self._yuzhi-1:
if self._sortlst[st]>self._sortlst[ed]:
#print('子区间划分最后交换')
self._swap(st,ed)
return
#print('划分区间：(', st, ',', ed, ')')
pivot=self._sortlst[self._Get_mediom(st,ed)]
p1=st+1
p2=ed-1
while True:
while self._sortlst[p1]<pivot:
p1+=1
while self._sortlst[p2]>pivot:
p2-=1
if p1 >= p2:
break
self._swap(p1,p2)
p1+=1
p2-=1
self._sort(st,p1-1)
self._sort(p2+1,ed)
def Sort(self,lst):
#print()
#print('原始输入：',lst)
self._sortlst=lst
self._sort(0,len(self._sortlst)-1)
return self._sortlst
调用方法：
quick=QuickSort()
print('排序结束：',quick.Sort([2,1]))
print('排序结束：',quick.Sort([4,3,2,1]))
print('排序结束：',quick.Sort([1,2,3,4,5,6,7,8,9]))
print('排序结束：',quick.Sort([6,6,6,6,6,6,6,6]))
运行结果：
原始输入： [2, 1] 子区间划分最后交换 2 1 交换后： [1, 2] 排序结束： [1, 2] 原始输入： [4, 3, 2, 1] 划分区间：( 0 , 3 ) 4 3 交换后： [3, 4, 2, 1] 1 3 交换后： [1, 4, 2, 3] 3 4 交换后： [1, 3, 2, 4] 中值点index： 1 ,值 3 3 2 交换后： [1, 2, 3, 4] 排序结束： [1, 2, 3, 4] 原始输入： [1, 2, 3, 4, 5, 6, 7, 8, 9] 划分区间：( 0 , 8 ) 中值点index： 4 ,值 5 划分区间：( 0 , 3 ) 中值点index： 1 ,值 2 划分区间：( 5 , 8 ) 中值点index： 6 ,值 7 排序结束： [1, 2, 3, 4, 5, 6, 7, 8, 9] 原始输入： [6, 6, 6, 6, 6, 6, 6, 6] 划分区间：( 0 , 7 ) 中值点index： 3 ,值 6 6 6 交换后： [6, 6, 6, 6, 6, 6, 6, 6] 6 6 交换后： [6, 6, 6, 6, 6, 6, 6, 6] 6 6 交换后： [6, 6, 6, 6, 6, 6, 6, 6] 划分区间：( 0 , 3 ) 中值点index： 1 ,值 6 6 6 交换后： [6, 6, 6, 6, 6, 6, 6, 6] 划分区间：( 4 , 7 ) 中值点index： 5 ,值 6 6 6 交换后： [6, 6, 6, 6, 6, 6, 6, 6] 排序结束： [6, 6, 6, 6, 6, 6, 6, 6]
