Python中的堆排序

Question

出于某种原因，我的堆排序运行得比应该的慢了好几倍：

def heapsort(unsrt):
   if len(unsrt) == 1:
      return unsrt
   elif len(unsrt) == 2:
      if (unsrt[0] > unsrt[1]):
         unsrt.append(unsrt.pop(0))
      return unsrt
   for i in range((len(unsrt)-2)/2,-1,-1):
      root = i
#      print unsrt
      while True:
         left = root * 2 + 1#left child
         rght = left+1      #right child
         if len(unsrt)-1 < rght: #if you've reached the end
            break
         if len(unsrt) >= rght and unsrt[left] < unsrt[rght]:
            left += 1
            rght += 1
         if unsrt[root] < unsrt[left]:
            unsrt[root], unsrt[left] = unsrt[left], unsrt[root]
            root = left
         else:
            break

   unsrt.append(unsrt.pop(0))
   unsrt[:-1] = heapsort(unsrt[:-1])
   return unsrt

我觉得它的运行速度是 n^2 (log n)^2，但我不太确定怎么才能降低这个复杂度。有没有办法把它调整到正确的复杂度呢？unsrt 是一个未排序的数组。

Answer 1

我觉得问题出在这一行：

unsrt.append(unsrt.pop(0))
unsrt[:-1] = heapsort(unsrt[:-1])

基本上，如果我理解你的实现没错的话，你每次调用时都在对数组进行堆化，找出最大值，把它放到数组的最后一个位置，然后再重复这个过程。

我能指出三个问题：

1. pop(0) 的运行时间是 O(n)，因为你调用了n 次，所以总的时间复杂度是 O(n²)
2. unsrt[:-1] 会创建一个列表的副本，这也是 O(n)，虽然由于内存优化它运行得很快，但这仍然是浪费时间
3. 这一点我不太确定，如果我错了请纠正我。你的堆化算法的时间复杂度是 O(nlogn)，而你运行了n 次，所以总的时间复杂度是 O(n² logn)。你应该只对数组进行一次堆化，这可以在O(nlogn)（实际上可以在O(n)内完成），然后再删除最小值n 次。从堆中删除一个元素的时间复杂度是 O(logn)，所以总的操作时间将是 O(nlogn)

所以我会这样做：

1. 单独写一个堆化函数（让堆的头部是最小值）
2. 单独写一个删除最小值的函数
3. 在排序函数中，只需对数组进行一次堆化，然后删除最小值n 次。

使用这个方法，你就不需要在数组中移动元素了。当你从堆中删除一个元素时，它会自动被推到数组的最后一个未排序的位置。