排序--快速排序

结合这几周的面试来看，快速排序可以说是面试必问的问题之一了，今天就来彻底将这部分内容梳理一下。

这篇文章中，作者提出了他非常好奇的三个问题：

快排为啥叫快排，快排是所有排序里面性能最好的吗？

快排适合什么情况呢，还是无论什么情况下快排总是最好的（显然No）？

快排算法的思想是什么？其性能优良的原因是依赖于算法中的哪个部分？

作者给出的回答是：

快排的性能在所有排序算法里面是最好的，数据规模越大快速排序的性能越优。快排在极端情况下会退化成 的算法，因此假如在提前得知处理数据可能会出现极端情况的前提下，可以选择使用较为稳定的归并排序。

首先，快排运用了二分的思想，首先选择一个基准，定义左右两端指针，先从右向左扫描，直到 a[j]=temp，将 a[i] 移动到 j 所在位置同时 j-- ，左右指针从数组两端往中间进行靠近，直到 i==j 。而快速排序则要进行多次快排过程，直到划分的区间最后长度仅为1。

总结下来就是：

选择a中的任意一个元素pivot（这里选择的是队首元素），以该元素为基准

将小于基准的元素移到左边，大于基准的元素移到右边（分区操作）

a被pivot分为两部分（pivot所在下标代表pivot在a中的排序），继续对剩下的两部分做同样的处理

直到所有划分的区间长度仅为1

void Quick_Sort(int a[],int left,int right) {

if(划分长度大于等于2，即left

int i=left,j=right,temp=a[left];

while(i

while(i=temp)

j--;

if(i

a[i]=a[j]; //发现小于基准的元素，将其替换到左半区

i++; //继续往中间靠

}

while(i

i++;

if(i

a[j]=a[i]; //发现大于基准的元素，将其替换到右半区

j--;

}

}

a[i]=temp; //基准值是被覆盖掉的，将其添加回数组

Quick_Sort(a,left,i-1); //递归继续进行快排

Quick_Sort(a,i+1,right); //若前面没有进行副本拷贝，递归操作就不太好判断边界了

}

}

图源：https://www.cnblogs.com/alvinai/p/12623792.html

总结上面过程就是：先从右开始对比，之后小于则替换 left 并移动 left ，然后新 left 对比 base 若大于则替换 right 并移动 right ，然后新 right 对比 base ，left 和 right 重合后用 base 替换。它的时间复杂度 取决于base值真实在排序后的位置，如果 base 刚好为排序中间的位置，时间复杂度为 O(nlogn)，如果 base 为数列最大值或最小值，则为O(n2 ）。

为什么快速排序是平均性能最好的排序算法，其优渥之处体现在哪？

首先，如果我们已经知道 a

第二，假如我们已知，a

算法分析：