Python Quicksort算法排序不正确

Question

正如标题所示，我的Python Quicksort代码遇到错误。我的代码在下面，这是我正在测试的输入文件。

5
3
8
6
7
4
9
2
1
10

在代码中，变量i是边界值，变量j是要与枢轴进行比较的当前值。问题是，当Partition执行其第一次迭代时，数组中的3值不会像预期那样在枢轴值（在本例中为5）的左侧结束。顺便说一句，我总是以最左边的索引为枢轴。

def Partition(input_array, left_index, right_index):
    pivot_value = input_array[left_index]

    i = left_index + 1
    for j in range(i+1, right_index):
        if input_array[j] < pivot_value:
            swap(input_array, i, j)
            i = i + 1

    swap(input_array, left_index, i - 1)
    print(input_array)
    return i - 1

def swap(input_array, i, j):
    input_array[i], input_array[j] = input_array[j], input_array[i]
    return input_array

这是数组之前 Partition的第一次迭代：

5, 3, 8, 6, 7, 4, 9, 2, 1, 10

这是数组之后 Partition的第一次迭代：

1, 4, 2, 5, 7, 3, 9, 8 , 6, 10

如您所见，3位于错误的位置。任何帮助，将不胜感激！

Answer 1

从for j索引开始i+1循环时，算法不会发现3<5，也不会推进i索引。删除+1

参考Lomuto scheme here