Python 3 快速排序实现不工作

Question

我是运行一个在列表上进行快速排序的测试脚本因为在快速排序中有很多分区和选择主元素的方法

我在这里使用选择列表的第一个索引作为枢轴 pivot=list[0] 然后进行排序 pivot_pos=quicksort(list,l,h)

l: 下界 & h:Higher/Upper 界

在 returning 适当的主元索引后，列表分为两部分这样：

LEFT PART:quicksort(list,l,pivot_pos-1)&

RIGHT PART:quicksort(list,pivot_pos+1,h)

因为枢轴的位置是 returned 我们不把他包含在下一个递归调用中

quicksort函数快速分区，而partition函数return属于枢轴元素的索引。

完整代码如下：

#!/usr/bin/env python3

# quicksort by selecting first element as pivot

def partition(list,l,h):
 pivot=list[l]
 i=l
 j=h

 while(i<=j):
  if list[i]<pivot:
   i+=1
  if list[j]>pivot:
   j-=1
  if (list[i]> pivot and list[j]<pivot):
   list[i],list[j]=list[j],list[i]

 list[j],pivot=pivot,list[j]
 return j

def quicksort(list,l,h):
 if l<h:
  pivot_pos=partition(list,l,h)
  quicksort(list,l,pivot_pos-1)
  quicksort(list,pivot_pos+1,h)



def main():
 list=[] # empty list
 # creating a user defined list
 n=int(input('Define length of array:'))
 for a in range(0,n):
  x=int(input('list{}='.format(a)))
  list.append(x)
 l=0
 h=int(len(list)-1)
 print("l:",l)
 print("h:",h)
 print('Before Sorting:',list)
 quicksort(list,l,h)
 print('After Sorting:',list)

main()

这是编写快速排序的好方法，因为它不涉及太多循环，使时间复杂度尽可能低

但代码无法正常工作，只是卡住了你可以在这里看到o/po/p_of_code

对于不熟悉快速排序的人Read-It here

Answer 1

将您的 parition 替换为以下内容：

def partition(lst,l,h):
 pivot=lst[l]
 i=h
 for j in range(h, l, -1):
  if lst[j] > pivot:
   lst[i],lst[j]=lst[j],lst[i]
   i-=1
 lst[i],lst[l]=lst[l],lst[i]
 return i

注意：我完全重写了这个答案。我发布的原始答案不正确。这是一个更标准的解决方案，我已经对其进行了测试，它可以处理我所有的测试用例。此版本使用第一个元素作为基准。

Python 3 快速排序实现不工作

Python 3 Quicksort Implementation Not Working

python

algorithm

sorting

data-structures

quicksort