_关于快速排序的笔记 __ _

基于小闫老师视频的基础上，我总结了我自己关于快速排序的看法

话不多说看代码

void quick_sort(int q[],int l,int r)
{
if(l>=r) return; //判断这一数组是否存在，通俗说一段数字如果左边起始位置比右起始位置大，理论上不存在
int x=q[l+r>>1],i=l-1,j=r+1; //设置变量 x为我们的参照值
//比较过程
while(i[HTML_REMOVED]x);
if(i<j) swap(q[i],q[j]);
else break;
}
quick_sort(q,l,j);//两个递归
quick_sort(q,j+1,r);
}
//以上为代码实现，接下来解析

假设一段数字吧
3 1 2 5 4
n=5
排序时就知道了l=0,r=n-1=4,
x=q[l+r>>1]=q[(l+r)/2]=q[2]=2;
i=l-1,j=r+1,这是为了更方便的处理边界，不细说记住即可
3 1 2 5 4
i j
3>2,即q[i]>x,i 不移动
4>2,即q[j]>x,j 前移
3 1 2 5 4
i j
同上述过程相似
3>2,即q[i]>x,i 不移动
5>2,即q[j]>x,j 前移
3 1 2 5 4
i j
此时3>2,即q[i]>x,i 不移动
2=2,即q[j]=x,j 不移动
两者交换
2 1 3 5 4
i j
2=2,即q[i]=x,i 不移动
3>2,即q[j]>x,j 前移
2 1 3 5 4
i j
2=2,即q[i]=x,i 不移动
1<2,即q[j]<x,j 不移动
两者交换
1 2 3 5 4
i j
1<2,即q[i]<x,i后移
2=2,即q[j]=x,j 不移动
1 2 3 5 4
i
j
i不小于j,跳出循环
开始递归quick_sort(q,0,1)
quick_sort(q.2,4)