Python快速排序只是部分排序

我正在學習快速排序算法，但由於某種原因，此python實現的輸出只是部分排序，我得到了'最大遞歸深度達到'較大的輸入。在過去的幾天裏，我一直在抨擊我的頭，我知道這可能是一件非常愚蠢的事情，但我似乎無法弄清楚，所以我會很感激任何幫助。Python快速排序只是部分排序

def ChoosePivot(list): 
    return list[0] 

def Partition(A,left,right): 
    p = ChoosePivot(A) 
    i = left + 1 

    for j in range(left + 1,right + 1): #upto right + 1 because of range() 
     if A[j] < p: 
       A[j], A[i] = A[i], A[j] #swap 
       i = i + 1 
    A[left], A[i - 1] = A[i-1], A[left] #swap 
    return i - 1 

def QuickSort(list,left, right): 
    if len(list) == 1: return 
    if left < right: 
     pivot = Partition(list,left,right)    
     QuickSort(list,left, pivot - 1) 
     QuickSort(list,pivot + 1, right) 
     return list[:pivot] + [list[pivot]] + list[pivot+1:] 

sample_array = [39,2,41,95,44,8,7,6,9,10,34,56,75,100] 
print "Unsorted list: " 
print sample_array 
sample_array = QuickSort(sample_array,0,len(sample_array)-1) 
print "Sorted list:" 
print sample_array

來源

2012-04-06 Manish Gill

你應該考慮更高層次的算法。這就是你如何用C這樣的語言寫出來的。在功能上考慮它會更好。 – 2012-04-06 06:19:56

不entirley肯定這是問題，但你錯艇員選拔支點：

def ChoosePivot(list): 
    return list[0] 
def Partition(A,left,right): 
    p = ChoosePivot(A) 
    ....

您始終以原始列表的頭部，而不是修改列表的頭部。

假設您在某一時刻將範圍縮小到了左= 5，右= 10 - 您選擇了列表[0]作爲關鍵點 - 這並不好。
其結果是，在每一個地方left>0你忽略列表中的第一個元素，迭代「小姐」這 - 這可以解釋部分分揀

來源

2012-04-06 06:55:13 amit

謝謝，就是這樣。乾杯阿米特！ – 2012-04-06 07:29:10

def ChoosePivot(list): 
    return list[0]

正如阿米特說，這是錯誤的。你想要p = A[left]。但是，還有另一個問題：

if A[j] < p: 
    A[j], A[i] = A[i], A[j] #swap 
i = i + 1

樞軸索引只應在交換時增加。作爲if聲明的一部分，將i = i + 1縮進與交換深度相同。

獎金問題：你爲什麼分區兩次？

來源

2012-04-06 07:14:05

對不起，這兩個都是格式錯誤。 – 2012-04-06 07:28:46

也最後交換;

A [左]，A [I - 1] = A [I-1]，A [左] #swap

應該與樞軸完成。

除此之外，Quicksort在原地工作。所以你不需要下面的回報;

返回列表[：透視] + [列表[透視] +列表[支點+ 1：]

來源

2012-04-06 10:35:58 sardok

-1

不完全的回答你的問題，但我相信它仍然是最相關的。

實現快速排序時始終在同一位置選擇一個樞軸是該算法的一個缺陷。人們可以生成一系列數字，使得算法在O（n^2）時間內運行，並且絕對運行時間可能比bubblesort更差。

在算法中，選擇最左邊的項目會使算法在數組已經排序或接近排序的最差情況下運行。

樞軸的選擇應該隨機執行以避免此問題。

檢查算法在維基百科上執行問題：http://en.wikipedia.org/wiki/Quicksort#Implementation_issues

其實，檢查孔的文章。這值得你花時間。

來源

2012-08-24 12:25:48 Francisco

隨機選擇一個支點只會減少在最壞情況下運行的可能性，因爲沒有什麼能夠阻止計算機隨機選擇最差的支點 - 所以說隨機選擇可以避免這個問題是不正確的。另一種選擇主軸以避免在二次時間內運行快速排序的方法是使用三中值方法 - 取第一個，最後一個和中間值，並選擇中間值。 – Steve 2012-11-09 22:37:57

Python快速排序只是部分排序

回答

相關問題