​ 先贴一段百度：快速排序采用的是分治思想，即在一个无序的序列中选取一个任意的基准元素key，利用key将待排序的序列分成两部分，前面部分元素均小于或等于基准元素，后面部分均大于或等于基准元素，然后采用递归的方法分别对前后两部分重复上述操作，直到将无序序列排列成有序序列。

1.从待排序的数列中选择一个基准值，称为key值。

2.重新排列数列，所有比基准值小的数放到基准左边，所有比基准值大的数放到基准右边，(相同的数随意放那边都行)。在这一次排序过后，该基准就处于数列的中间位置。这个称为分区操作。

3.递归的重复执行上一步基准值的左右数列，递归到最后，数组的长度是1时，也就是已经排好序。

1、快速排序采取的是分治法的思想，可以看到每次分区操作都是将一个序列分解为两个序列，当序列长度为0或者1时，则此序列是排好序的。

2、快速排序算法是不稳定的，何为不稳定，何为稳定，不稳定指对于在序列中两个相同的元素，在排序后他们的前后顺序发生了变化，而稳定则相反，有些人可能会想，我两个元素都是相同的，谁前谁后不都一样吗？但在实际的开发中，真实情况往往是复杂的，比如：对一组学生元素进行排序，要求先按照学号进行排序，再按照成绩进行排序，如果第二次排序采用的是不稳定的排序算法，将导致成绩相同的学生学号不是有序的。

1、选取基准，例如选取第一个元素作为基准，申明左右指针分别指向数组的头尾

2、将右指针向左移动，当当前元素小于基准时停下

3、将左指针向右移动，当当前元素大于基准时停下

4、将两个指针的值进行交换

5、循环2-4步骤，直到左右指针相遇

6、将基准值跟指针指向位置的值进行交换

至此，基准的左边元素都小于等于基准，基准的右边元素都大于等于基准，再递归将左右子数组也按照刚才的步骤处理即可。

实现代码如下：

1、选取基准，例如选取第一个元素作为基准（把基准挖掉），申明左右指针分别指向数组的头尾

2、将右指针向左移动，当当前元素小于基准时停下，并将当前元素挖走，填到左指针指向的位置（坑）

3、将左指针向右移动，当当前元素大于基准时停下，并将当前元素挖走，填到右指针指向的位置（坑）

4、继续走第2跟第3步，直到左指针跟右指针相等

5、再将基准填到指针指向的位置

至此，基准的左边元素都小于等于基准，基准的右边元素都大于等于基准，再递归将左右子数组也按照刚才的步骤处理即可。

代码实现如下：

1、选取基准，例如选取第一个元素作为基准，申明pre指针（前指针）指向序列开头(index=0)，cur指针（后指针）则为pre+1

2、将cur指针向右移动，直到遇到比基准小的元素

3、将pre指针向右移动一位（+1），如果pre跟cur不相等，则交换两个指针的元素

4、继续重复2-3步骤，直到cur指针到序列尾

5、将pre指针位置的元素跟基准进行交换

至此，基准的左边元素都小于等于基准，基准的右边元素都大于等于基准，再递归将左右子数组也按照刚才的步骤处理即可。

代码实现如下：

第一种是取随机值做下标
第二种是获取这三个数中不是最大，也不是最小的那个值的下标，这种情况下不会有最坏情况，因为有三数组取中。

我们只需将取基准值时的方法改为三数取中即可达到优化效果。