首页 » python » 正文

python 排序 快速排序

快速排序的实质就是我们指定一个数组中的值,比如第一个值,然后我们找到这个值的位置,位置的要求事,这个位置左侧都是<=这个值的, 右边都是>=这个值的,然后就分成了两个数组,然后递归对这个两个数组进行此方法

例如

6 9 3 4 1

我们取key=6

然后,两个指针,分别从数组的两侧开始向中间靠拢

lp 从 0 开始 ary[lp]=ary[0]=6 满足 <= 6 ,继续,lp=lp+1, 然后,ary[lp]=ary[1]=9 不满足 <=key的值,所以第一次我们得到的lp为1

然后我们看rp

rp=4 ary[rp]=ary[4]=1 不满足 >=6 ,所以,rp=4

然后互换两个元素得到的结果事

6 1 3 4 9

先看rp,rp=4 ,ary[rp]=ary[4]=9 满足 >=6,rp=rp-1 ;rp = 3  ary[rp]=ary[3]=4 不满足 >=6,所以rp=3

这个时候lp=1 ,这个时候的ary[lp]=ary[1]=1 满足 <=6 ,lp=lp+1 ,lp=2 ,这个ary[lp]=ary[2]=3 满足 <=6 ,lp=lp+1; lp=3 ,这个时候ary[lp]=ary[3]=4 满足 <=6,但是,这个时候lp=rp了,所以最终的结果是

rp=3

lp=3

互换后不变

6 1 3 4 9

这个时候我们就找到这个位置了,我们把ary[left]和ary[lp]互换后得到

4 1 3 6 9

6 的左边都小于 6 ,右边都大与 6

然后递归

 

 

 

 

 

 

 

 

 

发表评论