堆排序利用堆的特性对数组进行排序。它涉及构建一个用于递增顺序排序的最大堆，其中在根处包含堆的最大元素。对于降序排序，使用最小堆，它在根处包含堆的最小元素。堆排序的升序排序的过程步骤总结如下:
- 第1步:构建一个最大堆，其中根部包含堆的最大元素
- 第 2 步: 将堆的最后一个元素与根元素交换，并从堆中删除最后一个元素。对其余元素重复步骤 1。
示例:
要了解堆排序，让我们考虑一个未排序的数组[10, 1, 23, 50, 7, -4] 并讨论按升序对数组进行排序所采取的每个步骤。
下图中显示了输入数组和最大堆的堆结构。堆的根元素的索引号为0。在最大堆中，堆的最大元素始终位于根。
构建初始最大堆后，堆的最后一个元素与根元素以及包含数组中最大的数将从堆中删除。之后，对堆中剩余的元素使用heapify函数，使其成为最大堆，元素数量将减少1。这个过程一直持续到堆中的元素数量为1。此时，数组将被排序。
上图描述了从堆中消除最大元素以及从堆的剩余元素形成最大堆。该过程的最终结果是一个升序排序的数组。
堆排序的实现
public class MyClass {
// 调用heapify函数的堆排序函数
//构建最大堆，然后交换最后一个元素
// 第一个元素的最大堆
//从堆中排除最后一个元素并重建堆
static void heapsort(int Array[]) {
int n = Array.length;
int temp;
for(int i = n/2; i >= 0; i--) {
heapify(Array, n-1, i);
}
for(int i = n - 1; i >= 0; i--) {
//将最大堆的最后一个元素与第一个元素交换
temp = Array[i];
Array[i] = Array[0];
Array[0] = temp;
//从堆中排除最后一个元素并重建堆
heapify(Array, i-1, 0);
}
}
// heapify函数用于构建最大堆
//最大堆在根处有最大元素，这意味着
//数组的第一个元素将是最大堆中的最大值
static void heapify(int Array[], int n, int i) {
int max = i;
int left = 2*i + 1;
int right = 2*i + 2;
//如果左边元素大于根
if(left <= n && Array[left] > Array[max]) {
max = left;
}
//如果右侧元素大于根
if(right <= n && Array[right] > Array[max]) {
max = right;
}
//如果最大值不是i
if(max != i) {
int temp = Array[i];
Array[i] = Array[max];
Array[max] = temp;
//递归地堆化受影响的子树
heapify(Array, n, max);
}
}
//打印数组的函数
static void PrintArray(int Array[]) {
int n = Array.length;
for (int i=0; i<n; i++) {
System.out.print(Array[i] + " ");
}
System.out.println();
}
//测试代码
public static void main(String[] args) {
int[] MyArray = {10, 1, 23, 50, 7, -4};
int n = MyArray.length;
System.out.println("原始数组");
PrintArray(MyArray);
heapsort(MyArray);
System.out.println("\n排序数组");
PrintArray(MyArray);
}
} 上面的代码将给出以下输出:
原始数组
10 1 23 50 7 -4
排序数组
-4 1 7 10 23 50 时间复杂度:
创建堆的时间复杂度为θ(N)，创建最大堆的时间复杂度为θ(logN) em> 堆排序的总体时间复杂度为 θ(NlogN)。