如何計算快速排序中的交換？ （蟒蛇）

Question

你好，我有這樣的代碼，我不知道如何計算有多少交流呢:(

def quicksort(lista,izq,der): 
i = izq 
j = der 
pivote = lista[(izq + der)//2] 

while i <= j: 
    while lista[i] < pivote: 
     i += 1 
    while pivote < lista[j]: 
     j -= 1 
    if i <= j: 
     aux = lista[i] 
     lista[i] = lista[j] 
     lista[j] = aux 
     i += 1 
     j -= 1 

if izq < j: 
    quicksort(lista, izq, j); 
if i < der: 
    quicksort(lista, i, der); 

所以我在哪裏可以把一個櫃檯，說我有多少交流呢？ 編輯：我需要的函數返回我該號碼，這多少比較呢

Answer 1

這裏就是我會做，如果我理解你的權利

def quicksort(lista,izq,der): 
    i = izq 
    j = der 
    swap_count = 0 
    compare_count = 0 
    pivote = lista[(izq + der)//2] 

    while i <= j: 
    while lista[i] < pivote: 
     i += 1 
    while pivote < lista[j]: 
     j -= 1 
    if i <= j: 
     aux = lista[i] 
     lista[i] = lista[j] 
     lista[j] = aux 
     swap_count += 1 
     i += 1 
     j -= 1 
    compare_count += 1 

    if izq < j: 
    other_swap, other_compare = quicksort(lista, izq, j) 
    swap_count += other_swap 
    compare_count += other_compare 
    if i < der: 
    other_swap, other_compare = quicksort(lista, i, der) 
    swap_count += other_swap 
    compare_count += other_compare  

    return (swap_count, compare_count) 

這樣你在掉期增加。和recursi的比較正如你所做的那樣。

Answer 2

def quicksort(lista,izq,der): 
    i = izq 
    j = der 
    pivote = lista[(izq + der)//2] 

    swap_count = 0 
    while i <= j: 
     while lista[i] < pivote: 
     i += 1 
     while pivote < lista[j]: 
     j -= 1 
     if i <= j: 
     aux = lista[i] 
     lista[i] = lista[j] 
     lista[j] = aux 
     swap_count += 1 
     i += 1 
     j -= 1 

    if izq < j: 
     swap_count += quicksort(lista, izq, j) 
    if i < der: 
     swap_count += quicksort(lista, i, der) 

    return swap_count