如何在快速排序中计数交换次数？（Python）

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

在编程中，有时候我们会遇到一些问题，特别是在使用某些工具或库的时候。这些问题可能会让我们感到困惑，尤其是当我们不太了解这些工具的工作原理时。

比如说，有人可能在使用某个特定的编程语言时，遇到了错误或者不明白某个功能是怎么用的。这种情况下，大家通常会去网上查找答案，像是StackOverflow这样的论坛就是一个很好的地方。在这里，很多有经验的程序员会分享他们的解决方案和经验。

在提问的时候，清楚地描述你遇到的问题是非常重要的。这样其他人才能更好地理解你的情况，并给出有效的建议。通常，提供一些代码示例或者错误信息会帮助别人更快地找到问题所在。

总之，编程过程中遇到问题是很正常的，关键是要善于寻求帮助，并且在提问时尽量详细和清晰。

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

Answer 2

如果我理解你的意思没错的话，我会这样做。

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)

这样一来，你在进行递归调用的时候，就可以把交换和比较的操作都加进来了。