我对Max Heap Sort的伪代码中有一部分感到困惑。 down to 2是什么意思?
HeapSort(A)
Build-Max-Heap(A)
for i <-- length[A] <b><i>down to 2</i></b>
do exchange A[1] <---> A[i]
heap-size[A] = heap-size[A] -1
Max-Heapify(A,1)
我对Max Heap Sort的伪代码中有一部分感到困惑。 down to 2是什么意思?
HeapSort(A)
Build-Max-Heap(A)
for i <-- length[A] <b><i>down to 2</i></b>
do exchange A[1] <---> A[i]
heap-size[A] = heap-size[A] -1
Max-Heapify(A,1)
这意味着你要针对{length[A],length[A]-1,length[A]-2,...,2}
中的每个i值重复执行该块。
如果这是C语言(或C++、Java——这些语言的语法都相同),可以这样写:
for (int i = length(A), i >= 2, i--) {
do...
}
堆排序本质上是选择排序,但未排序的数组部分以最大堆数据结构的形式存储。更具体地说,堆排序的工作方式如下。首先选择数组A [1..n]中的最大元素,并将其与A [n]交换。然后选择数组A [1..n-1]中的最大元素,并将其与A [n-1]交换。重复此过程,直到在最后一次迭代中,我们发现A [1..2]中的最大元素并将其与A [2]交换。此时,元素A [2..n]处于正确的位置,因此A [1]也处于正确的位置,数组已排序。
这几乎就像选择排序(在其中我们将从A [1..i]中选择最大元素并将其与A [i]交换),只是在堆排序中,A [1..i]使用称为最大堆的数据结构存储,因此选择最大元素的过程不是使用线性搜索(如选择排序中那样),而是通过使数组成为最大堆并将最大元素带到第一个位置A [1]。因此,找到最大元素需要log n时间而不是线性时间。
以上算法可以表述为:对于 i=n, n-1, ..., 2(按此顺序),在 A[1..i] 中找到最大的元素并将其与 A[i] 交换。由于 i 按这种递减顺序取值,因此 for 循环可以写为:for i = n downto 2。