算法知识总结-快速排序

[zzusunjs]

作者快速排序算法的实现似乎没有考虑到 数组中有相同元素的情况。 在把元素划分到 pivot 两侧的时候，如果遇到 和 pivot 值相同的元素，就会出现错误。如输入为 [5,1,1,2,0,0] 时。

    while (array[end] > pivot && start < end) {
      end--;
    }

    // 将比枢纽值小的值交换到 start 位置
    array[start] = array[end];

    // 移动 start 值，当 start 指针指向的值小于枢纽值时，start 指针向后移动
    while (array[start] < pivot && start < end) {
      start++;
    }

    // 将比枢纽值大的值交换到 end 位置，进入下一次循环
    array[end] = array[start];

可以改成：

    while (array[end] >= pivot && start < end) {    // 处理 和 pivot 值相等的元素
      end--;
    }

    // 将比枢纽值小的值交换到 start 位置
    array[start] = array[end];

    // 移动 start 值，当 start 指针指向的值小于枢纽值时，start 指针向后移动
    while (array[start] < pivot && start < end) {
      start++;
    }

    // 将比枢纽值大的值交换到 end 位置，进入下一次循环
    array[end] = array[start];

[CavsZhouyou]

感谢指正，这种情况确实忽略了，文档已经修正。