快排的优化方法
找基准方面的优化
聚集相同元素法：在经过一次找基准之后把数据中与基准相同的数据聚集到基准左右，优化后：由于相等元素被聚集在一起，递归时跳过这些元素，减少了比较和交换的次数，减少了递归深度
随机取基准法：产生随机数在数据中去取随机位置元素为基准
三分取基准：比较数据中start、end和两者中间位置的数据的大小，将这三个值处于中间位置的值放到首位，再进行找基准操作
当序列长度达到一定大小时，使用插入排序
- 当快排达到一定深度后，划分的区间很小，里面的元素已经基本有序了，再使用快排的效率不高
- 当待排序列的长度达到一定数值后，可以使用插入排序
- 当待排序列长度为5~20之间时，使用插入排序可以避免一些有害的退化情形
尾递归优化
- 快排跟大多数分治排序算法一样，都有两次递归调用，区别：归并排序的递归在函数一开始，快排的递归在函数尾部，这就使得快排可以使用尾递归优化
- 尾递归概念：函数所有递归形式的调用都出现在函数的尾部，当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归
- 尾递归特点：在回归过程中不用做任何操作，编译器会利用这种特点自动生成优化的代码
- 尾递归原理：当编译器检测到一个函数调用时尾递归的时候，它就会覆盖当前的活动记录而不是在栈中去创建一个新的。因为尾递归是最后一条待执行语句，所以当这个递归返回时栈帧并没有其他事情可做，也就没有保存栈帧的必要了。通过覆盖当前栈帧而不是在其之上重新添加一个，这样使用的栈空间大大缩减，使得实际的运行效率变高
多线程处理快排
- 分治法的基本思想是将一个问题分解为多个规模较小的子问题，这些子问题独立且与原问题相同，求解子问题，再将子问题的解合并得到原问题的解。所以在处理快排时可以使用多线程提高排序的效率