快速排序
单边循环快排
pv指向分区中最后一个元素,i,j指向分区中第一个元素,j所指向的元素和pv指向的元素比较大小,如果比pv所指大,则j++,否则与i所指元素交换位置,i++,j++;当j=pv时,j与i所指元素交换位置。i为分区位置。一直分区直到分区元素为1。程序伪码如下:
双边循环快排
pv和i指向第一个元素,j指向最后一个元素,j从后往前找到第一个比pv小的元素,i从前往后找第一个比pv大的元素,然后i和j所指元素交换位置,直到i和j重合,pv和i交换位置,i即分区位置。程序伪码如下:
如果先i再j,就会出现后面比pv大的值和pv交换了位置
如果内层循环不加上i<j的判断,就会导致j一直减到比i小,i一直增到比j大
如果a[i]不加等于pv,因为i一开始就是指向pv,那会把基准换走,后续比较结果全乱套
那为什么不直接i=l+1?