优化堆排序（Java 实例代码）

桃扇骨 2023-10-14 15:52 36阅读 0赞

**目录**

优化堆排序

Java 实例代码

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

--------------------

## 优化堆排序 ##

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

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

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

![f82d6d4241d72f006220f6076c36e788.png][]

#### Java 实例代码 ####

**源码包下载：**[Download![icon-default.png_t_N6B9][]https://www.runoob.com/wp-content/uploads/2020/09/runoob-algorithm-HeapSort.zip][Download_icon-default.png_t_N6B9_https_www.runoob.com_wp-content_uploads_2020_09_runoob-algorithm-HeapSort.zip]

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

package runoob.heap;  
  
import runoob.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\];  
\}  
\}

[f82d6d4241d72f006220f6076c36e788.png]: https://img-blog.csdnimg.cn/img_convert/f82d6d4241d72f006220f6076c36e788.png
[icon-default.png_t_N6B9]: https://csdnimg.cn/release/blog_editor_html/release2.3.5/ckeditor/plugins/CsdnLink/icons/icon-default.png?t=N6B9
[Download_icon-default.png_t_N6B9_https_www.runoob.com_wp-content_uploads_2020_09_runoob-algorithm-HeapSort.zip]: https://www.runoob.com/wp-content/uploads/2020/09/runoob-algorithm-HeapSort.zip