快速排序：用Python實現

Question

性能問題我想實現在Python 3快速排序算法使用該檢查等元素分區功能。

我的解決辦法似乎工作找到關於解決方案，但是已經需要長達40秒的長度爲10的陣列^ 5，這是相當極端。

我是相當新的Python和無法檢測是什麼原因導致的代碼運行緩慢這一點。

我使用下面的代碼：

import sys 
import random 

def partition3(a, l, r): 

    # bringing all elements less than or equal to x to the front 
    x = a[l] 
    j = l; 
    for i in range(l + 1, r + 1): 
     if a[i] <= x: 
      j += 1 
      a[i], a[j] = a[j], a[i] 
      #print('exchange happened:', a) 
    a[l], a[j] = a[j], a[l] 

    # shifting all elements with value x to the middle 
    cnt = j-1 
    xcnt = 0 
    i = l 
    while i < cnt: 
     if a[i] == x: 
      xcnt += 1 
      while a[cnt] == x and cnt > i: 
       cnt -= 1 
      a[cnt], a[i] = a[i], a[cnt] 
      cnt -= 1 
     i += 1 
    return j - xcnt, j 

def randomized_quick_sort(a, l, r): 
    if l >= r: 
     return 
    k = random.randint(l, r) 
    a[l], a[k] = a[k], a[l] 
    m1, m2 = partition3(a, l, r) 
    randomized_quick_sort(a, l, m1 - 1); 
    randomized_quick_sort(a, m2 + 1, r); 

我會很感激在這個問題上得到一些建議。

Answer 1

我發現這個問題：

在partition3(a,l,r)定義，而不是：

# shifting all elements with value x to the middle 
cnt = j-1 
xcnt = 0 
i = l 
while i < cnt: 
    if a[i] == x: 
     xcnt += 1 
     while a[cnt] == x and cnt > i: 
      cnt -= 1 
     a[cnt], a[i] = a[i], a[cnt] 
    i += 1 

我需要添加進一步xcnt += 1獲得等於樞軸元素的正確計數，從而使代碼變爲：

# shifting all elements with value x to the middle 
cnt = j-1 
xcnt = 0 
i = l 
while i < cnt: 
    if a[i] == x: 
     xcnt += 1 
     while a[cnt] == x and cnt > i: 
      cnt -= 1 
      xcnt += 1 
     a[cnt], a[i] = a[i], a[cnt] 
     cnt -= 1 
    i += 1 

這個錯誤導致數據集中表現不佳，因爲它包含非常多的相等值，因爲E以下的值的塊的長度被低估。因此，超過必要的函數調用更多的人已被處決，恢復解決方案基本上恢復到標準的快速排序，而不佔所有相等的元素。