掌握这道快速排序题，我成功获得百度面试offer
1.概念
快速排序，听这个名字就能想到它排序速度比较快方法，是一种分治思想，现在各种语言中自带的排序库很多使用的都是快速排序。
空间复杂度
快速排序是一种原地排序，只需要一个很小的栈作为辅助空间，空间复杂度为O(log2n)，所以适合在数据集比较大的时候使用。
时间复杂度
时间复杂度比较复杂，最好的情况是O(n)，最差的情况是O(n2)，所以平时说的O(nlogn)，为其平均时间复杂度。
2.基本思想
随机找出一个数，可以随机取，也可以取固定位置，一般是取第一个或最后一个称为基准，然后就是比基准小的在左边，比基准大的放到右边，如何放做，就是和基准进行交换，这样交换完左边都是比基准小的，右边都是比较基准大的，这样就将一个数组分成了两个子数组，然后再按照同样的方法把子数组再分成更小的子数组，直到不能分解为止。
3.举例说明
(一)算法思想
本质是分而治之思想的运用。首先选取一个元素作为主元(pivot)，将大于该主元的元素放在数组的右边，小于主元的元素放在数组的左边，等于主元的元素位置不变，然后不断迭代上述规则完成排序。
（1）主元pivot。取头、中、尾三处的中位数，并交换位置，使头中尾按照从小到大的顺序排放(*)。此时，运用一个trick，将mid处元素值与right-1处元素值交换。
（2）子集的划分。设置两个变量i和j，令i=left、j=right-1；第一次循环时，i=0，j=len(arr)-2。
（3）i每次向右移动一个位置(i++)，当该位置元素值大于等于主元时停止移动；此时，j向左移动，每次移动一个位置(j--)，当该位置元素值大于等于基准值时停止移动。
（4）交换i、j处的值，然后重复执行步骤3，直至i=j时，停止移动。交换i与right-1处值(即pivot值)。
（5）此时，pivot左边的都是小于其值，右边都是大于其元素的值。然后不断对左右部分递归执行上述4步骤。
注意点:
(1)主元的选取。如果取数组第一个元素A[0]，很大可能造成整个排序时间复杂度过高。例如A=[1,2,3,4,...,n]，此时选1作为主元，会使得T(N)=O(N)+T(N-1)=O(N)+O(N-1)+T(N-1)=O(N^2)，时间复杂度过大。
(2)主元存放的位置。主元确定后，left位于无序区的最左边，right位于无序区的最右边，left<mid<right。此时，将mid存放之right-1的位置，然后只需要比较left+1与right-2位置的元素与主元pivot的大小，并交换。
(3)与pivot相等元素的处理。在子集划分过程中，如果遇到与pivot值相等的元素，有两种选择，一种是把它视为小于pivot的元素(即i++或j--)，即忽略；另外一种是把它视为大于pivot的元素(i或j停下来，等待与j或i的交换)，即停下来作交换。考虑一种特殊的例子，A=[1,1,1,1,...,1]，如果选择忽略策略的话，此时i会不断向前移动，直至移动至j处(j位于pivot处，最右边)，时间复杂度T=O(N^2)。如果选择停下来作交换，原始序列会被基本上被等分成n/2的序列，然后不断往下递归，最后时间复杂度为O(NlogN)。
(4)何时停止划分。i=j处，交换i与pivot位置的值。
(5)不断迭代。pivot与i交换位置后，此时pivot左边全是小于等于主元值的元素，pivot右边全是大于等于主元值的元素。然后对左右部分，不断迭代使用快排。 (6)小规模数据的处理。由于不断递归，会占用系统堆栈的空间，且系统堆栈的进出很耗费时间，对于小规模数据，此时，插入排序优于快排。
(二)代码实现
def quick_sort(arr):
quicksort(arr,0,len(arr)-1)
def quicksort(arr,left,right):
pivot=median3(arr,left,right)
i=left+1
j=right-2
while(True):
while(A[i]<pivot):
i++
while(A[j]>pivot):
j--
if(i<j):
A[i],A[j]=A[j],A[i]
else:
break
A[i],pivot=pivot,A[i]
quicksort(arr,left,i-1)
quicksort(arr,i+1,right)
def median3(arr,left,right):
center=(left+right)/2
#left<center
if(A[left]>A[center]):
A[left],A[center]=A[center],A[left]
#left<right,保证left是最小的
if(A[left]>A[right]):
A[left],A[right]=A[right],A[left]
#center<right
if(A[center]>A[right]):
A[center],A[right]=A[right],A[center]
A[center],A[right-1]=A[right-1],A[center]
//统一接口
void qucik_sort(int A[],int N)
{
quicksort(A,0,N-1);
}
void quicksort(int A[],int left,int right)
{
int pivot=median3(A,left,right); //选取主元
int i=left,j=right-1; //一定要在上一句后面
for(;;) //子集划分
{
while(A[++i]<pivot)
{ }
while(A[--j]>pivot)
{ }
if(i<j)
swap(&A[i],&A[j]);
else
break;
}
swap(&A[i],&A[right-1]); //交换主元与i的值
//递归排序
quicksort(A,left,i-1);
quicksort(A,i+1,right);
}
voif median3(int A[],int left,int right)
{
int center=(left+right)/2;
if(A[left]>A[center]) //left<center swap(&A[left],&A[center]);
if(A[left]>A[right]) //left<right swap(&A[left],&A[right]);
if(A[center]>A[right])
swap(&A[center],&A[right]);
swap(&A[center],&A[right-1])
}
void swap(int a,int b)
{
int temp;
temp=a;
a=b;
b=temp;
}
(三)算法分析
优点：速度快，剩空间，缺点：非常脆弱，在实现时一定要注意几个小细节。
什么情况下是最好的呢：
待排序列升序有序O(n)，即，1 2 3 4 5 6 7，这种情况下，基准选择第一个数，调整次数最少，注意只是调试次数减少，比较次数没变少，
所以从理论上来说，比较只需要把数据放入寄存器，然后比较。
mov ax,
mov cx,
cmp ax,cx
但实际情况下，因为有L1，L2的存在，然后你的程序又存在进程切换，现场恢复等等各种复杂因素，实际上的速度就好说了。
什么情况下是最差的呢：
待排序序列降序有序O(n2)，即，7 6 5 4 3 2 1，这种情况就退化为冒泡排序。
最近面试被怼了？缺面试题刷提升自己吗？
点击:
来获取学习资料+面试题视频解析提升自己去挑战一下BAT面试难关吧
image
