快排为什么必须先从右往左查找（排升序）

这个问题感觉很多人在学快排的时候总是会忽略掉，我第一次学的时候也没有注意这个点，在网上看到的很多讲快排的博客里也没有提到这个问题，有些甚至是按照错误顺序来的。

    while (i < j && arr[j] >= pivot) {
        j--;
    }
 	while (i < j && arr[i] <= pivot) {
        i++;
    }

上述代码，比较的顺序不能改变。

假如排序序列为以下数组，两种顺序下得到的结果就是不同的。

	int[] arr = {6,1,2,7,9,8,4,5,10};

下面我们利用反证法来看看为什么不能先从左向右查找

假设按照以下代码，以Hoare法的思想进行排序：

 	while (i < j && arr[i] <= pivot) {
        i++;
    }
    while (i < j && arr[j] >= pivot) {
        j--;
    }

到这一步之后我们就能发现一个不和谐的因素，根据基准6，本应将8分在6的右面，现在却分到了左边。

因为 i 从左往右查找的话，每次停下来的位置对应的元素必然比基准要大，如果这时跳出循环的话，这个较大元素就会被换到前面，得到的结果就是错的；而先从右往左查找的话，停下来的位置对应的元素必然比基准要小，如果这时跳出循环的话，这个较小元素就会被换到前面。

所以，如果我们要排升序的序列，一定记得先从右往左查找！顺序不错，结果才会正确。

最后

以上就是无奈小土豆为你收集整理的快排为什么必须先从右往左查找（排升序）的全部内容，希望文章能够帮你解决快排为什么必须先从右往左查找（排升序）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。