Java实现快排+小坑+partition的两种思路

时间:2022-10-16 21:50:08

在做一道剑指Offer的题的时候,有道题涉及到快排的思路,一开始就很快根据以前的思路写出了代码,但似乎有些细节不太对劲,自己拿数据试了下果然。然后折腾了下并记录下一些小坑,还有总结下划分方法partition的两种思路。

partition思路1——交换思路

以待排序数组的第一个元素为基准值key,然后两个指针i和j,先从后面开始找(这个是个坑后面会总结)第一个比基准key小的数字,停下来,然后再从前面开始找第一个比基准key大的数字,停下来。

然后交换这两个指针的元素。

当两个指针相碰的时候,也就是i>=j了,或者说就i==j了(因为按照代码应该不存在i>j的情况),就再把a[begin]的值和a[i]或者a[j]的值交换就好了。

大概代码如下:

int key = a[begin];
int i = begin, j = end;//坑三i的值 while(i < j) {
//坑2顺序
//while(i < j && a[i] <= key)i++;//从左边开始找到第一个比key大的数字然后停下来
while(i < j && a[j] >= key)j--;//从右边开始找到第一个比key小的数字然后停下来
while(i < j && a[i] <= key)i++;//从左边开始找到第一个比key大的数字然后停下来 swap(a, i, j);
} swap(a, begin, i);//最后是i还是j的位置和begin交换都行,因为最后是i==j

partition思路2——填坑思路

想下我们的swap一般是怎么实现的: 

int temp = a[i];
a[i] = a[j];
a[j] = temp;

一开始把i位置的值存在一个地方,这相当于i位置有个坑了,因为其他数字可以覆盖i位置了。

填坑思路的写法就是根据这个思想。

一样是以待排序数组的第一个元素为基准,我们将a[begin]的值存在key的位置,然后begin就有个坑了吧。

然后两个指针,i从begin开始,j从end开始,一开始从后面也就是j从后往前遍历,找到第一个比key小的数字,然后把这个数字覆盖在i的位置上,因为i是从begin开始,而begin位置有个坑是可以填的。

好了j的东西既然写在了i的位置,意味着j的位置也是个坑了,这个时候i就开始往前遍历,找到第一个比key大的值,然后填在j的坑处,一直以此类推。

最后,i和j指针相碰后,只要把key的值填到最后i或者说是j的位置就好了。

看个大概代码:

int key = a[begin];//begin的位置被存了起来,这个时候可以利用begin的位置存其他值了

        int i = begin, j = end;

        while(i < j) {
while(i < j && a[j] >= key) j--;
//一开始进来i就是begin,本来begin的值已经在key那里相当于begin或者说是i这里有个坑所以可以覆盖
a[i] = a[j]; while(i < j && a[i] <= key) i++;
//a[j]的值刚刚已经放在之前的i位置了,相当于j的位置有坑可以覆盖
a[j] = a[i];
} a[i] = key;//最后填i或j都行了,因为最后一次肯定是i==j了

关于写快排代码过程中遇到的小坑

坑1:

Java实现快排+小坑+partition的两种思路

这个其实也不是坑拉,就递归流程中对结束条件的理解。一开始我就想着begin==end就结束,如果是begin>end就出错了。

但其实递归过程中是肯定会出现begin>end的情况的,因为partition+1和partition-1这一步。

所以正确的递归终结条件应该直接是begin >= end。    (提醒一下归并排序中的终结条件是begin == end)

坑2:

Java实现快排+小坑+partition的两种思路

坑2就是到底是先从后面往前找还是先从前面往后面找。

如果是填坑的思路就不会陷入这个坑中,因为你要先填a[i]或者说是a[begin]的坑,那么肯定是先从后往前遍历。

但如果是交换的思路就emmm我就踩辽。

因为如果你是先从前往后找,那么出去第一个循环的条件一定是找到第一个比key大的数字了。(不可能是因为i >=j,因为外层循环确保了i < j才进来);

但这个时候第二个循环可能因为i>=j而出去,那么这个时候,如果指针相碰了,i和j一起指向一个比key大的值,然后和a[begin]交换的话,就会出现一个比key大的值出现在key的左边,就错辽。

所以应该要先从后往前遍历这样就会找到第一个比key小的值就出去循环,第二个循环即使i=j了出去也不怕,因为这个时候和begin交换是没有问题的。

补充:这个while(i < j && a[i] >= key)中的i<j也是少不了的,不然的话有越界的危险

坑3:

Java实现快排+小坑+partition的两种思路

坑3是i是从哪里开始的,这个在填坑思路中也不会出错,因为第一个坑是在begin那里嘛所以肯定i是从begin开始……

然后我用交换思路的时候又采坑了,就想着反正是比较begin后面的数字嘛,就直接i从begin+1开始。

这样会有什么问题呢?

考虑只有三个数字:11,32,41;这其实已经是有序的了,那么i如果从begin+1开始,那么i会直接原地跳出循环,因为32是第一个比key11大的数字嘛;

然后j从右边开始遍历,也会停在32的位置,因为虽然42,32都比key大讲道理应该继续往下遍历的,但我们条件中还有i < j这一项,所以就停下来了。

然后出去循环,和begin交换——就变成32,11,41的错误答案了。

所以 i 要从begin开始噢。

补充小坑:

“交换思路”中,其实还有个小问题,就是条件那里应该只能够a[i]<=key,而不能是<。

因为如果是小于,那么第一次i就会原地停下,然后和a[j]交换。然后最后key归位我们是和begin和i交换的方式,但这个时候begin已经不是key了,就会出错。

实际上,如果改写成了a[i]<key的话,这个时候和“填坑思路”的效果就是一样的了。