Java堆排序算法详解与实现

"Java排序算法之堆排思想及代码实现" 在计算机科学中，堆排序是一种基于比较的排序算法，其核心思想是利用了数据结构中的堆（Heap）概念。堆是一个近似完全二叉树的结构，同时满足堆的性质：在大顶堆中，每个节点的值都大于或等于其子节点的值；在小顶堆中，则相反。Java中的堆排序主要分为两个阶段：构建堆和调整堆。 1. 构建堆（Heapify）： - 从最后一个非叶子节点开始，自底向上、自右向左遍历数组。对于每个节点，如果其值小于其子节点，就交换它们的位置，以确保该节点成为其子树的大顶堆根节点。 - 这个过程从倒数第二个非叶子节点（(n/2)-1，其中n是数组长度）开始，一直进行到根节点（下标为0）。 2. 调整堆（Heapify Down）： - 将数组的最大元素（堆顶元素）与最后一个元素交换，这样最大的元素就被放置到了正确的位置（数组末尾）。 - 将数组的大小减一（n--），此时新数组的大小为n。 - 对剩下的n个元素重新构建大顶堆，这个过程重复，直到数组只剩下一个元素。 以给定的整型数组arr={2,1,3,6,0,5}为例，我们来逐步解释堆排序的过程： 1. 初始化大顶堆： - 首先，数组arr已经是部分堆，但不是大顶堆。我们需要从第一个非叶子节点（下标为1）开始调整。 - 检查arr[1]（值为1），它小于其父节点arr[0]（值为2），所以我们保持不变。 - 接着检查arr[2]（值为3），发现3大于2，因此交换它们，得到新的数组arr={3,2,1,6,0,5}。 - 现在arr[2]（值为1）小于其父节点arr[1]（值为2），所以保持不变，堆化完成。 2. 堆排序： - 将堆顶元素（arr[0]）与最后一个元素（arr[5]）交换，得到arr={5,2,1,6,0,3}，数组大小减一（n=5）。 - 重新构建大顶堆，从arr[1]开始检查，发现1<2，保持不变；接着检查arr[2]，发现1<3，保持不变，堆化完成。 - 再次交换堆顶元素（arr[1]）与最后一个元素（arr[4]），得到arr={4,2,1,6,3,0}，数组大小再次减一（n=4）。 - 继续构建大顶堆，检查arr[1]，保持不变；检查arr[2]，1<2，保持不变，堆化完成。 - 交换堆顶元素（arr[1]）与最后一个元素（arr[3]），得到arr={3,2,1,4,3,0}，数组大小为3。 - 构建大顶堆，检查arr[1]，保持不变；检查arr[2]，1<2，保持不变，堆化完成。 - 最后，交换堆顶元素（arr[1]）与最后一个元素（arr[2]），得到arr={2,1,3,4,3,0}，数组大小为2，此时arr已经是有序的。 通过上述过程，我们成功地使用堆排序将无序数组arr={2,1,3,6,0,5}转换为了升序排列的数组arr={0,1,2,3,4,5}。 在Java中实现堆排序，我们可以定义一个方法来构建和调整堆，然后在一个循环中不断交换堆顶元素和末尾元素并缩小堆的大小。以下是一个简单的Java代码示例： ```java public class HeapSort { public static void sort(int[] arr) { int n = arr.length; // 构建大顶堆 for (int i = n / 2 - 1; i >= 0; i--) { heapify(arr, n, i); } // 交换并调整堆 for (int i = n - 1; i > 0; i--) { swap(arr, 0, i); heapify(arr, i, 0); } } private static void heapify(int[] arr, int n, int i) { int largest = i; // 初始化最大值为根节点 int left = 2 * i + 1; int right = 2 * i + 2; // 如果左子节点大于根节点，更新最大值 if (left < n && arr[left] > arr[largest]) { largest = left; } // 如果右子节点大于当前最大值，更新最大值 if (right < n && arr[right] > arr[largest]) { largest = right; } // 如果最大值不是根节点，交换它们并继续调整 if (largest != i) { swap(arr, i, largest); heapify(arr, n, largest); } } private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } ``` 这个Java代码实现了堆排序的基本逻辑，可以在任何Java环境中运行，对输入数组进行升序排序。