在 python 中无法获得快速排序的正确输出

Question

我正在尝试在 python 中编写快速排序算法，但我没有得到正确的输出。我正在通过用户输入获取数组。

这是我的代码。

def partition(arr, low, high):
    pivot = arr[low]
    i = low
    j = high

    while i < j:
        while arr[i] <= pivot: i = i+1
        while arr[j] > pivot: j = j-1
        if i < j:
            arr[i], arr[j] = arr[j], arr[i]

    if i > j:
        arr[j], arr[low] = arr[low], arr[j]
        return j


    def quickSort(arr, low, high):
        if low < high:
            pivot = partition(arr, low, high)
            quickSort(arr, low, pivot-1)
            quickSort(arr, pivot+1, high)
 

    a = []
    n = int(input("Enter the number of elements : "))
    print("Enter the elements now")
    for i in range(0, n):
        element = int(input())
        a.append(element)

    print("Given array :", a)
    l = len(a)

    quickSort(a, a[0], a[l-1])
    print("Sorted array is :", a)

Answer 1

这是一个快速排序实现：您很快就会发现哪里出错了：

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] < pivot:
            i += 1
            arr[j], arr[i] = arr[i], arr[j]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1


def quickSort(arr, low, high):
    if (low < high):
        pi = partition(arr, low, high)
        quickSort(arr, low, pi - 1)
        quickSort(arr, pi + 1, high)
    


def sort(arr):
    quickSort(arr, 0, len(arr) - 1)
    return arr

arr = [1,3,5,4,2,10]
print(sort(arr))

注意：这是原位排序

Answer 2

刚刚对您的代码进行了一些更改，其中存在多个逻辑问题（其中一个是您传递了数组中的值而不是传递索引），希望它能有所帮助

def partition(arr, low, high):
  pivot = arr[low]
  i = low + 1
  j = high

  while True:
      while i <= j and arr[j] >= pivot:
          j = j - 1

      while i <= j and arr[i] <= pivot:
          i = i + 1

      if i <= j:
          arr[i], arr[j] = arr[j], arr[i]
      else:
          break

  arr[low], arr[j] = arr[j], arr[low]
  return j

def quickSort(arr, low, high):
    if low >= high:
        return 

    pivot = partition(arr, low, high)
    quickSort(arr, low, pivot-1)
    quickSort(arr, pivot+1, high)


a = []
n = int(input("Enter the number of elements : "))
print("Enter the elements now")
for i in range(0, n):
    element = int(input())
    a.append(element)

print("Given array :", a)

quickSort(a, 0, len(a) - 1)
print("Sorted array is :", a)

在 python 中无法获得快速排序的正确输出

Not getting correct output for quick sort in python

python

quicksort