Java函数实现堆排序的完整流程和代码
堆排序是一种基于比较的排序算法，它利用了堆这种数据结构的特性。堆是一种完全二叉树，它有两个重要的性质：父节点的键值总是大于或等于（小于或等于）任何一个子节点的键值；每个节点的左子树和右子树都是一个堆。通俗来说，就是根节点是最大或者最小值，每个父节点的值都大于或者小于孩子节点的值。接下来，我们将通过实例来了解堆排序的完整流程和代码实现。
1.建堆
首先，将待排序的序列构造成一个大根堆，即每个父节点的值都大于或等于自己的孩子节点，这里使用的是最大堆。
代码实现：
public static void buildMaxHeap(int[] arr, int length) {
for (int i = length / 2; i >= 1; i--) {
heapify(arr, length, i);
}
}
其中，arr是待排序的数组，length是数组的长度，i是节点的位置。
2.堆调整
在建堆完成后，通过堆调整，将堆的结构调整为满足每个父节点的值都大于或等于自己的孩子节点。
代码实现：
public static void heapify(int[] arr, int length, int i) {
int left = 2 * i;
int right = 2 * i + 1;
int largest = i;
if (left <= length && arr[left - 1] > arr[i - 1]) {
largest = left;
}
if (right <= length && arr[right - 1] > arr[largest - 1]) {
largest = right;
}
if (largest != i) {
swap(arr, i - 1, largest - 1);
heapify(arr, length, largest);
}
}
其中，arr是待排序的数组，length是数组的长度，i是节点的位置，left是i节点的左孩子，right是i节点的右孩子，largest是最大值的位置。
3.堆排序
在完成堆调整后，将堆的根节点（最大值或最小值）与最后一个叶子节点交换，并去掉最后一个叶子节点。接着，重新调整堆的结构，找到最大值或最小值，重复以上过程，直到排序完成。
代码实现：
public static void heapSort(int[] arr, int length) {
buildMaxHeap(arr, length);
for (int i = length; i >= 1; i--) {
swap(arr, 0, i - 1);
length--;
heapify(arr, length, 1);
}
}
其中，arr是待排序的数组，length是数组的长度。
4.完整代码
public class HeapSort {
public static void main(String[] args) {
int[] arr = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7};
heapSort(arr, arr.length);
print(arr);
}
public static void heapSort(int[] arr, int length) {
buildMaxHeap(arr, length);
for (int i = length; i >= 1; i--) {
swap(arr, 0, i - 1);
length--;
heapify(arr, length, 1);
}
}
public static void buildMaxHeap(int[] arr, int length) {
for (int i = length / 2; i >= 1; i--) {
heapify(arr, length, i);
}
}
public static void heapify(int[] arr, int length, int i) {
int left = 2 * i;
int right = 2 * i + 1;
int largest = i;
if (left <= length && arr[left - 1] > arr[i - 1]) {
largest = left;
}
if (right <= length && arr[right - 1] > arr[largest - 1]) {
largest = right;
}
if (largest != i) {
swap(arr, i - 1, largest - 1);
heapify(arr, length, largest);
}
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void print(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}
5. 总结
通过以上实例，我们了解到了Java函数实现堆排序的完整流程和代码。堆排序是一种非常高效的排序算法，时间复杂度为O(nlogn)，缺点是不稳定，适用于大数据量的排序。