Quicksort的Python實現無法對整個數組進行排序

Question

我對Quicksort算法有下面的python代碼。該代碼工作正常，直到所有元素的權利的樞紐大於樞紐，在這種情況下，這些仍然未排序。

理論上的代碼應該在陣列中的所有元素進行排序，但在這個階段，我不知道我失蹤

def swap(array, i, j): 
    temp = array[i] 
    array[i] = array[j] 
    array[j] = temp 

def choosePivotFirstElement(array, left, right): 
    return left 

def partition(array, pivotIndex, left, right): 
     swap(array, pivotIndex, left) #put pivot to the left 
     pivot = array[left] 
     i = left + 1 

    for j in range(left+1, right+1): 
      if (array[j] < pivot): 
        swap(array, i, j) 
        i = i + 1 
    swap(array, left, i-1) #put pivot back to its place 
    return (i-1) #return the position of the pivot 

def qsort(array, left, right): 
     if ((right - left) < 2): 
      return 

     pivotIndex = choosePivotFirstElement(array, left, right) 
     split = partition(array, pivotIndex, left, right) 

     qsort(array, left, split) 
     qsort(array, split + 1, right) 
     return array 

myList = [7,2,5,1,29,6,4,19,11] 
sorted = qsort(myList,0,len(myList)-1) 
print sorted 

，應返回

[1，2，4，5 ，6，7，11，19，29]

而是返回

[1，2，4，5，6，7，29，19，11]

我是python的新手，所以我可能會犯一個相當明顯的錯誤。

Answer 1

你的代碼看起來不像一個python代碼，你仍然試圖從某種東西轉換爲python，這不是一個好主意。

通常你有這樣的事情在Python：

def quickSort(arr): 
    #Leftside 
    less = [] 
    #pivot 
    pivotList = [] 
    #rightside 
    more = [] 
    #if the length of the array is one. then, there is no point in sorting it 
    if len(arr) <= 1: 
     return arr 
    else: 
    #sorting :) 
     #Defines the pivot as the first element 
     pivot = arr[0] 
     for i in arr: 
      #for each element in the array verify: 
      if i < pivot: 
       less.append(i) 
      elif i > pivot: 
       more.append(i) 
      else: 
       pivotList.append(i) 
     #Define the Lists less (left side) and more (right side) 
     less = quickSort(less) 
     more = quickSort(more) 
     #Return the actual array 
     return less + pivotList + more 

a = [7, 2, 5, 1, 29, 6, 4, 19, 11] 
a = quickSort(a) 
print a 

編輯

有在代碼中幾個錯誤，因爲所指出的評論：

你應該沒有交換功能，因爲你可以做

array[i], array[j] = array[j], array[i] 

既然你沒有在這個例子中調用，選擇PivotLastElement或choosePivotMedianofThree，所以你不應該發佈它們。在其他問題中，您可以稍後詢問具體的事情。

發帖之前請先閱讀How to Create a Minimal, Complete and Verifiable Example。

範圍應該是範圍（左+ 1，右+ 1）：

而且我有一個印象是：

if ((right - left) < 2)應該像我在我的代碼中使用：if len(array) <= 1:

在代碼的後面你可以看到你沒有定義其他列表，而且你也不會返回任何東西。請再次查看我的代碼並嘗試理解它。你可能會問關於具體細節的問題，，但你真的應該試着去理解它。