Python 快速排序不对右侧进行排序

Question

这是我的输入：

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

这是我的代码（由于尚未实现的另一个原因调用 count）：

def Count(num_list):
global comparisons


if len(num_list) > 1:
    pivot = num_list[0]
    print "Pivot value is: %s, current list is: %s" % (pivot, num_list)
    i = 1
    j = 1

    for j in range(len(num_list)):
        if num_list[j] < pivot:
            print "Swapping %s and %s" % (num_list[i], num_list[j])
            num_list[i], num_list[j] = num_list[j], num_list[i]
            print "List is now: %s" % (num_list)
            i += 1


    num_list[0], num_list[i-1] = num_list[i-1], num_list[0]
    print "List before next recursive step: %s" % num_list

    Count(num_list[:(len(num_list)/2)])
    Count(num_list[(len(num_list)/2):])

print "List at the end of function: %s" % (num_list)

我得到以下结果：

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

当我查看我所做的所有调试打印语句时，我发现右半部分的组合方式与左半部分的组合方式不同，但我想不通。

Answer 1

@Natecat 和@rcgldr 感谢您为我指明了正确的方向。我的代码只是在第一次进行排序，因为递归调用正在对从未返回的数组切片副本进行排序。这违背了原地排序的快速排序的定义。我更新为以下并且有效。

def Count(num_list, first, last):
    if first < last:
        global comparisons
        comparisons += len(num_list)-1

        pivot = num_list[first]
        i = first + 1

        # quick sort
        for j in range(first+1,last):
            if num_list[j] < pivot:
                num_list[i], num_list[j] = num_list[j], num_list[i]
                i += 1

        # swap pivot with border index
        num_list[first], num_list[i-1] = num_list[i-1], num_list[first]

        # recurse
        Count(num_list, first, i-1)
        Count(num_list, i, last)

Python 快速排序不对右侧进行排序

Python quicksort not sorting right side

python

sorting

algorithm

quicksort