快速排序算法中的一些小细节_3. 考虑当基准元素选择为最右边的元素r[high]时,划分函数需不需要修改?

作者：繁依Fanyi0 | 2024-08-19 15:16:37

踩

3. 考虑当基准元素选择为最右边的元素r[high]时,划分函数需不需要修改?

选定基准值后，开始进行查找时的查找顺序（升序）：
如果基准值选取最左边的元素（low），那么查找顺序应该先从右往左（high-low），再从左往右（low-high）；
类似的，如果基准值选取最右边的元素（high），那么查找顺序应该先从左往右（low-high），再从右往左（high-low）；

原因：（第一种情况）如果查找顺序先是先从左往右（low-high）的话，会出现比基准值大的元素和基准值交换的情况。如序列：1,4,5，3,2 ；指针先从左往右（low-high）寻找大于1的元素，会停在元素4这个位置，然后从右往左（high-low）寻找小于1的元素，指针也会停在元素4这个位置（指针相遇就不会再往前寻找），所以此时会把元素4和基准值1交换，导致基准值置位错误。

总结：**（以上情形）**要保证基准值置位正确就要保证相遇点的元素值小于基准值，所以查找顺序必须先从右往左（high-low），再从左往右（low-high）。其余情形以及降序的情况由此可类推。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/1002821