算法结束时，left指针指向的值的大小与left指针的位置有何关系？

首先，来自维基百科的Hoare划分：

    T mid = arr[end];
    int left = start, right = end - 1;
    while (left < right) {
        while (arr[left] < mid && left < right) left++;
        while (arr[right] >= mid && left < right) right--;
        std::swap(arr[left], arr[right]);
    }
    if (arr[left] >= arr[end])
        std::swap(arr[left], arr[end]);
    else
        left++;

可以看到，最后left指针指向的值分为两种情况讨论，一种是大于等于pivot(即arr[end])，一种是小于pivot。我想要弄明白其中对应的left位置信息。

这需要从循环的结束条件开始。

首先可以明确，结束循环时，必然有left == right;

然后，有两种可能使得left == right:

1. 内部第一个循环while(arr[left] < mid && left < right) left++

   在left==right的前一个状态，即left = right - 1时，必然有arr[left] < mid ， 所以才能继续移动；最后，left指向了right的位置。停止循环。后面的循环也直接跳过。

   所以问题的关键是right是何种状态？同样有两种：

   1. right仅仅是初始化时的状态——即end-1，此时其与pivot的值大小还不能确定！因为它们还完全没有比较过。

   2. right是以后过后的状态；可以确定其指向的值必然大于等于pivot;

2. 内部第二个循环退出

   类似，现在需要讨论left指向的元素的大小。

   首先，要到第二个循环，必然有left < right且!(arr[left] < mid)，这是因为进第二个循环必然需要left小于right，又要退出第一个循环，则只能违背arr[left] < mid的条件。

   那么当right后退指向到left时，必然left位置的元素必然大于等于pivot.

综上，其实只有一种情况下left指向元素的值可能小于pivot， 就是当 0 ~ right-1 间的元素全都小于pivot时，left指针一次移动到right位置，right位置与pivot元素间的大小关系不确定。此时又有两种情况，如果小，那么可以说明， 0 ~ end-1 全都都是小于pivot的，此时换分位置就应该是end!

最后，只有一个结论：++left的结果，就等于end.

上半年就推出了这个结论，不过当时似乎没有记录。再回来看时，又有些不太清楚了。当然，这对于我们写划分毫无影响。只是弄明白结束条件更加清晰。