面试官最爱问的排序算法——快速排序
1、算法思想：
是一种升级版的冒泡，只不过它不是比较交换相邻的两个元素，它是跳跃性的比较交换远方的元素。
在数组中随便选一个基准数，一趟快速排序，可以让基准数左边的元素都比基准数小，基准数右边的都比基准数大。
然后继续以这种方式，在左右两边的数组中，递归排序，直至最终整体有序。
2、动图演示：
3、算法描述：
第一步
从数组中选择一个轴点元素（Pivot element），一般选择0位置元素为轴点元素
第二步
利用Pivot将数组分割成2个子序列
将小于 Pivot的元素放在Pivot前面（左侧） 将大于 Pivot的元素放在Pivot后面（右侧） 等于Pivot的元素放哪边都可以(暂定放在左边)
第三步
对子数组进行第一步、第二步操作，直到不能再分割(子数组中只有一个元素)
如下图：
begin指针会不会大于end?
begin最终会等于end!!
只要begin==end说明这次的轴点元素已经选择成功！！
4、代码实现：
// arr 需要排序的数组
// low 开始时最左边的索引=0
// high 开始时最右边的索引=arr.length-1
public static void quickSort(int[] array, int low, int high) {
if (low > high) {
return;
}
int left = low; // 左边的指针索引
int right = high; // 右边的指针索引，两边往中间靠拢
int pivot = array[left]; // 选取基准数为，待排序数组左边第一个元素。（其实下标为随机数最好）
while (left<right) { // 左右两边交替扫描，直到left = right
while (left < right && pivot <= array[right]) { // 从右往左扫描，找到第一个比基准值pivot小的元素，就退出本次while循环，后面执行交换。
right--; // 没找到，指针往左移动，继续比较。
}
// 这里暂时先不交换，等到从左往右扫描时，找到了比pivot大的数，再交换左右两个元素。可以减少一次交换的操作。
while (left < right && pivot >= array[left]) { // 上面从右往左的指针right已经停止，接下来跳到从左边往右边扫描。
left++; // 从左往右扫描，找到第一个比基准值pivot大的元素，就退出本次while循环，指针停在这里，后面要执行交换。
} // 没找到，指针往右移动，继续比较
// 此时指针停止，array[left]比pivot大，array[right]比pivot小，要交换他们的位置。
if (left < right) { // 交换前，确保left和right还没有相遇
// 优化==》使用异或的方式交换两个值
int temp = array[left]; // 临时变量，用来交换元素的。（用异或方式交换变量值可以不需要这个）
array[left] = array[right];
array[right] = temp;
}
}
// 一趟while循环后，left=right， 基准值要归位了。
array[low] = array[left]; // 此时基准值还在数组左边第一个位置，array[low]的位置，要与array[left]交换，
array[left] = pivot;
quickSort(array, low, right-1); // 递归调用pivot左半数组
quickSort(array, right+1, high ); // 递归调用pivot右半数组
}
解法二：
// 方法二：像归并一样分为两个函数，一个执行递归分组，一个执行分组内排序，让该分组内的基准值归位
public static int[] quickSort(int[] array, int low, int high) {
if (low < high) {
int mid = partition(array, low, high);
quickSort(array, low, mid - 1);
quickSort(array, mid+1, high);
}
return array;
}
public static int partition(int[] array, int low, int high) {
int pivot = array[low]; // 选取左边数组第一个元素为基准数（也可以随机选取）
while (low < high) { // 因为这里是调用partition的方式传入low与high的形参，所以不需要额外定义left和right指针了。
while (low < high && pivot <= array[high] ) { // 从右往左扫描
high--;
}
array[low] = array[high]; // 此时只交换了一次，array[low]的值在pivot上，不会丢失，等最终结束后才会进行归位
while (low < high && pivot >= array[low] ) { // 从左往右扫描
low++;
}
array[high] = array[low];
}
array[low] = pivot; // 基准值归位
return low;
}
5、算法分析：
（1）最坏时间复杂度
最坏情况是指每次区间划分的结果都是基准关键字的左边（或右边）序列为空，而另一边区间中的记录仅比排序前少了一项，即选择的关键字是待排序记录的最小值或最大值。最坏情况下快速排序的时间复杂度为O(n2)。
（2）最好时间复杂度
最好情况是指每次区间划分的结果都是基准关键字的左右两边长度相等或者相差为1，即选择的基准关键字为待排序的记录的中间值。此时进行比较次数总共为 nlogn，所以最好情况下快速排序的时间复杂度为O(nlogn)。
（3）平均时间复杂度
快速排序的平均时间复杂度为O(nlogn)。在所有平均时间复杂度为O(nlogn)的算法中，快速排序的平均性能是最好的。
（4）空间复杂度
快速排序的过程中需要一个栈空间来实现递归。最好情况，递归树的深度为log2n，其空间复杂度也就是O(nlogn)；最坏情况下，需要进行 n-1次递归，其空间复杂度为O(n)；平均情况，空间复杂度为O(nlogn).
（5）基准关键字的选取，基准关键字的选取是决定快速排序算法的关键，常用的基准关键字的选取方式如下：
第一种：三者取中。将序列首、尾和中间位置上的记录进行比较，选择三者中值作为基准关键字。
第二种：取left和right之间的一个随机数m(left<m<right)，用n[m]作为基准关键字。采用这种方法得到的快速排序一般称为随机的快速排序。
最佳情况：T(n) = O(nlogn)最差情况：T(n) = O(n2) 平均情况：T(n) = O(nlogn)
快速排序并不是稳定的。这是因为我们无法保证相等的数据按顺序被扫描到和按顺序存放。
快速排序在大多数情况下都是适用的，尤其在数据量大的时候性能优越性更加明显。但是在必要的时候，需要考虑下优化以提高其在最坏情况下的性能
我爱大风和烈酒，
也爱孤独和自由。