快速排序详解

今天我们来讲解一下快速排序

首先由我为大家介绍一下快速排序，快速排序算法最早是由图灵奖获得者Tony Hoare 设计出来的，他在形式化方法理论以及ALGOL60编程语言的发明中都有卓越的贡献，是20世纪最伟大的计算机科学家之一。而这快速排序算法只是他众多贡献中的一个小发明而已。

更牛的是，我们将要学习的这个快速排序算法，被列为20世纪十大算法之一。我们这些玩编程的人还有什么理由不去学他呢？

快排的核心思想是分治。通过一趟排序将待排记录分割成独立的两个部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。

进行快排的大体步骤可以分为3步：

1.确定分界点

我们可以选择的点有四种，第一种是左端点，第二种是右端点，第三种是中电，第四种是区间内的随机值

2.调整区间

3.递归处理左右两段

我们要说的第一种实现方式是暴力实现：

1.设置数组a[],b[]

2.遍历给出的数组，q[i]<x的，放入a数组，q[i]>x的，放入b数组。

3.最后将a,b数组排入q数组

但这个方法需要额外开辟空间，今天我们来讲解另外一种方法：

我们采用两个指针的做法，即设置指针i,指针j。i指向左端点，j指向右端点，先移动i,若满足条件q[i]<q[(l+r)>>1]，则i继续向下一位移动。若不满足，则i停下，再移动j，若满足条件q[j]>q[(l+r)>>1],则j继续移动，若不满足，则交换i,j停下时所指的数。

同时在代码实现过程中，容易涉及边界问题，如果记住模板则可以非常容易的写出。

模板如下：

void quick_sort(int q[],int l,int r)
{
 if(l>=r) return ;
int i=l-1,j=r+1,x=q[(l+r)>>1];
while(i<j)
{
  do i++;while(q[i]<x);
  do j--;while(q[j]>x);
  if(i<j)  swap(q[i],q[j]);
}
quick_sort(q,l,j),quick_sort(q,j+1,r);
}

 对于代码中的swap函数，如果编译器没有此函数，可以用以下代码替换：

int t;
t=q[i];
q[i]=q[j];
q[j]=t;

以下是程序代码实现：

#include <iostream>
 
using namespace std;
const int N =1e6+10;
int n;
int q[N];
void quick_sort(int q[],int l,int r)
{
if(l>=r) return ;
int i=l-1,j=r+1,x=q[(l+r)>>1];
while(i<j)
{
  do i++;while(q[i]<x);
  do j--;while(q[j]>x);
  if(i<j) swap(q[i],q[j]);
}
 quick_sort(q,l,j),quick_sort(q,j+1,r);
}
int main()
{
 scanf("%d",&n);
 for(int i=0;i<n;i++) scanf("%d",&q[i]);
  quick_sort(q,0,n-1);
for(int i=0;i<n;i++) printf("%d ",q[i]);
return 0;
 
}