经典排序算法回顾：

排序算法有非常多，应用也非常多，在各种笔试面试中也常常出现，所以现在就来复习一下相关的排序算法吧！
下面会介绍多种排序算法，在此之前先说一下，排序算法的评价主要有以下几个方面：

排序算法的时间复杂度；
排序算法的空间复杂度；
排序算法的稳定性
其中前两个是老生常谈了，基本提到算法都会考虑这两点。第三点中排序算法的稳定性是指如果待排序列中存在相同元素时，经过排序之后相同元素的先后顺序是否被打乱，如果保持不变则说明这个排序算法是稳定的，否则称该排序算法是不稳定的。

1.快速排序（quickSort）
快速排序是最常见的排序算法之一，需要重点掌握，要能够手撕代码的程度。
快速排序其实用了分而治之 的策略，它的一个核心思想就是：选择一个枢纽（pivot），通过元素交换使得比pivot小的元素在它左边，比它大的元素在它右边，再分别对左右两边做相同的操作。

快速排序的执行时间与数据序列的初始排列和基准值选取有关，
最好的情况下 每次选择的主元都能够正中的划分序列，此时的时间复杂度是T(N)=O(N*logN)，
在最坏的情况下 ，每次选择的主元都是极值的话，时间复杂度会达到T(N)=O(N^2)。（这个可以想象，如果每次主元都是最大值的话，那么划分相当于无意义，每次都要将剩余的所有元素进行排序，这样起不到快速排序的效果）

快排的实现过程中有两个重要的步骤：

选主元（pivot）
选主元为何重要，根据前面提到的快排的时间复杂度就可以知道，选取主元会非常大程度影响快排的效率。
一般情况下，最经典的选取主元方式就是任意头/中/尾的其中一个，这是最方便的做法。但是如果遇到本身已经有序的极端情况，选择头或尾作为主元就会非常危险。
那么也可以选择取头/中/尾的中位数作为主元（mid_of_3）。
或者可以随机选择一个未排序序列中的数作为主元，这也是有效的降低取到极值概率的办法。