【算法】简单理解快速排序(图解)
i负责找到比基准数大的数,调换到右边。
j负责找到比基准数小的数,调换到左边。
i和j相遇时,把基准数放到中间。
这里强调要j先出发(从小到大排序)。
所以最后的相遇是:
①j找到一个比基准数小的数,停下了,然后i再移动遇上j。所以相遇是在j找到的数的位置上,j负责找到比基准数小的数,所以和基准数调换,放到左边没有问题。
②j没有找一个比基准数小的数,直接遇上了i。i的位置保存了上次与j调换的结果,所以i上的数是比基准数小的,所以和基准数调换,放到左边没有问题。