先右j再左i --记快速排序里的一个大坑

2016-10-11  本文已影响506人  b6aed1af4328

快速排序用2个指针,左i右j,如果先左i循环,即

while(arr[i]<=temp&&i<j)
      i++;
while(arr[j]>=temp&&i<j)
     j--;

经由

if(i<j)
{ t=arr[i];
  arr[i]=arr[j];
  arr[j]=t;
}

左右交换,不断移除路上的绊脚石,终会达到i=j。此时i左边的数均小于temp,右边的数均大于temp。

但请注意,由于左i先行的缘故,此时arr[i]>temp

这意味着,之后arr[left]与arr[i]交换,把一个大于temp的数放到了第一位,要是此时i=2,岂不是把一个不是最小的数固定在了第一位!
而右j先行的话就不会,i=j时arr[i]是小于temp的。
还是先右j再左i的好。

上一篇 下一篇

猜你喜欢

热点阅读