在python中创建快速排序的分区函数

Question

嗨，我不能在python中为快速排序创建分区函数。我在很多网站上搜索过，但不知道是怎么回事。我试着去做，但被困在这里了。在

totalElem = input("Enter total Elements: ")
c = 0
unsortElem = [0]*totalElem
low = 0
high = totalElem - 1

# This is to input elements
for c in range(totalElem):
    unsortElem[c] = input("Enter Number: ")
    c += 1

# The swap function
def swap(elem1, elem2):
    k=elem1
    elem1 = elem2
    elem2 = k

def partition(list, low, high):
    left = low
    right = high
    pivot = (low+high)/2
    pivotElem = list[pivot]
    while(left<right):
        while(list[left]<pivotElem):
            left += 1
        while(list[right]>pivotElem):
            right += 1
        if(list[left]>list[right]):
            swap(left, right)


#The below prints are just to check if the function is getting correct values.
    print list
    print pivotElem
    print left
    print len(list)



partition(unsortElem, low, high)

Answer 1

您的代码中有几个错误-首先，您的right += 1是错误的，因为right是最高的索引。你需要减少值，而不是增加。其次，为什么要增加输入中的c？您正在使用range，因此它会自动执行。另外，您不需要自己的swap函数，因为Python可以这样做，而且list是一种类型，所以不能这样命名变量。在

你要做的是递归地对比你的轴心更小和更大的元素进行排序。如果在列表的开头找到比pivot大的元素，则停止，对于列表末尾较小的元素也是一样，然后交换值（因为它们在列表的不好的部分）。如果有更多相同的元素，您还需要注意。你的分区函数不仅仅做分区，因为你在那里交换元素，这更像是没有递归调用的不正确的快速排序函数。在

totalElem = int(raw_input("Enter total Elements: "))
unsortElem = []

# This is to input elements
for c in range(totalElem):
    unsortElem.append(int(raw_input("Enter Number: ")))

def qsort(mylist, low, high):
    if high - low < 1:   # there is less than 2 elements
        return
    left = low
    right = high
    pivotElem = mylist[(low + high) / 2]
    while left <= right:
        while mylist[left] < pivotElem:
            left += 1
        while mylist[right] > pivotElem:
            right -= 1
        if left <= right and mylist[left] >= mylist[right]:
            mylist[left], mylist[right] = mylist[right], mylist[left]
            left += 1
            right -= 1
    qsort(mylist, low, right)
    qsort(mylist, left, high)


qsort(unsortElem, 0, len(unsortElem) - 1)
print unsortElem

您没有提到您使用的是Python3还是Python2。对于python2，这是正确的，如果您希望python3使用它，只需使用input而不是raw_input和大括号进行打印，例如print(unsortElem)。在