Hoare分区不正确？

Question

我正在使用Python来实现Hoare Partition。代码如下，非常简单。

#!/usr/bin/env python 
#-*- coding:utf-8 -*-

def partition(li,start,end):
    print(li)
    x=li[start]
    i=start-1
    j=end+1
    while True:
        while True:
            j-=1
            if x>=li[j]:
                break
    
        while True:
            i+=1
            if x<=li[i]:
                break   
        if i<j:
            li[i],li[j] = li[j],li[i]
            print("i:", i)
            print("j:", j)
            print(li)
        else:
            return j

def main():
    li=[13,19,9,5,12,8,7,4,11,2,6,21] 
    print(partition(li,0,11))


if __name__ == '__main__':
    main() 

但我没有得到正确的答案。输出类似于：

[6, 2, 9, 5, 12, 8, 7, 4, 11, 19, 13, 21]

j=8，因为

li[j]=11

，但是左边部分中间还有一个12。当我手动运行这个程序时，我得到了相同的结果。

我是否遗漏了一些导致分区函数工作错误的东西？

Answer 1

这就是为什么我鼓励使用除了正整数或数字字符串之外的任何东西来对示例进行排序：
为值获取索引太容易了，反之亦然。

过程的排列没有任何问题，返回值也没有什么问题。
您的评估有误： 索引 8 未返回，因为该值是 11。
您确实not围绕11进行分区（结束索引，“非Python式”包含！？），但是

li[0]

的原始值：13。
返回 8 是因为返回时列表的右端有三个至少为 13 的值，第一个索引为 9。
返回的少一个是实现错误、错误、±1 错误。
12 留在左边部分是指定的：12 小于或等于 13。