优化堆排序

精华

小牛编辑

141浏览

2023-03-14

上一节的堆排序，我们开辟了额外的空间进行构造堆和对堆进行排序。这一小节，我们进行优化，使用原地堆排序。

对于一个最大堆，首先将开始位置数据和数组末尾数值进行交换，那么数组末尾就是最大元素，然后再对W元素进行 shift down 操作，重新生成最大堆，然后将新生成的最大数和整个数组倒数第二位置进行交换，此时到处第二位置就是倒数第二大数据，这个过程以此类推。

整个过程可以用如下图表示：

Java 实例代码

src/heap/HeapSort.java 文件代码：

package heap ;

import sort.SortTestHelper ;

/**
* 原地堆排序
*/
public class HeapSort <T extends Comparable > {

public static void sort ( Comparable [ ] arr ) {

int n = arr. length ;

// 注意，此时我们的堆是从0开始索引的
// 从(最后一个元素的索引-1)/2开始
// 最后一个元素的索引 = n-1
for ( int i = (n - 1 - 1 ) / 2 ; i >= 0 ; i -- )
shiftDown (arr, n, i ) ;

for ( int i = n - 1 ; i > 0 ; i -- ) {
swap (arr, 0, i ) ;
shiftDown (arr, i, 0 ) ;
}
}

// 交换堆中索引为i和j的两个元素
private static void swap ( Object [ ] arr, int i, int j ) {
Object t = arr [i ] ;
arr [i ] = arr [j ] ;
arr [j ] = t ;
}

// 原始的shiftDown过程
private static void shiftDown ( Comparable [ ] arr, int n, int k ) {

while ( 2 * k + 1 < n ) {
//左孩子节点
int j = 2 * k + 1 ;
//右孩子节点比左孩子节点大
if (j + 1 < n && arr [j + 1 ]. compareTo (arr [j ] ) > 0 )
j += 1 ;
//比两孩子节点都大
if (arr [k ]. compareTo (arr [j ] ) >= 0 ) break ;
//交换原节点和孩子节点的值
swap (arr, k, j ) ;
k = j ;
}
}

// 测试 HeapSort
public static void main ( String [ ] args ) {

int N = 100 ;
Integer [ ] arr = SortTestHelper. generateRandomArray (N, 0, 100000 ) ;
sort (arr ) ;
// 将heapify中的数据逐渐使用extractMax取出来
// 取出来的顺序应该是按照从大到小的顺序取出来的
for ( int i = 0 ; i < N ; i ++ ) {
System. out. print (arr [i ] + " " ) ;
}
// 确保arr数组是从大到小排列的
for ( int i = 1 ; i < N ; i ++ )
assert arr [i - 1 ] >= arr [i ] ;
}
}