先右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的好。