堆排序java实验报告

时间: 2023-06-29 18:20:30 浏览: 46
实验目的: 通过本实验,实现对堆排序算法的理解,掌握堆排序算法的原理以及实现方法,并掌握Java语言的编程技巧。 实验内容: 堆排序是一种树形选择排序方法,是对直接选择排序算法的有效改进。堆排序的基本思想是:将待排序的序列构造成一个大根堆或小根堆,堆顶元素为最大值或最小值,然后将堆顶元素与最后一个元素交换,然后把剩余的元素重新构造成堆。如此反复执行,直到排序完成。由于堆排序算法的时间复杂度为O(nlogn),因此在大数据量的情况下,堆排序是高效的。 堆排序算法的实现主要有两个步骤:构建初始堆和堆排序。其中,构建初始堆是将待排序的序列构建成一个大根堆或小根堆的过程,堆排序是不断将堆顶元素与最后一个元素交换,并重新调整堆的过程。 以下是Java语言实现堆排序的代码: ```java public class HeapSort { public static void heapSort(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--) { // 将堆顶元素与最后一个元素交换 int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // 调整堆 heapify(arr, i, 0); } } // 调整堆 public 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) { int temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp; heapify(arr, n, largest); } } public static void main(String[] args) { int[] arr = { 64, 34, 25, 12, 22, 11, 90 }; heapSort(arr); System.out.println("排序后的数组:"); for (int i = 0; i < arr.length; i++) System.out.print(arr[i] + " "); } } ``` 实验结果: 经过测试,以上代码能够正确地对数列进行堆排序,得到正确的排序结果。 实验总结: 通过本次实验,我学习了堆排序算法的原理和实现方法,并通过Java语言编写了相应的代码。堆排序算法具有高效的时间复杂度,在大数据量的情况下具有明显的优势。这次实验让我对Java语言的编程技巧有了更深刻的理解,也对算法的实现有了更深的认识。

相关推荐

插入排序是一种简单直观的排序算法,它的基本思想是将一个新元素插入到已排序好的数组中,使插入后的数组仍然有序。 下面是插入排序的Java代码实现: java public static void insertionSort(int[] arr) { int len = arr.length; for (int i = 1; i < len; i++) { int temp = arr[i]; int j = i - 1; while (j >= 0 && arr[j] > temp) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = temp; } } 我们可以通过比较不同数据规模下插入排序的运行时间来分析其效率。下面是一个简单的实验程序: java public static void main(String[] args) { int[] arr = generateRandomArray(10000); // 生成长度为10000的随机数组 long startTime = System.currentTimeMillis(); // 记录排序开始时间 insertionSort(arr); long endTime = System.currentTimeMillis(); // 记录排序结束时间 System.out.println("插入排序耗时:" + (endTime - startTime) + "毫秒"); } 我们可以将数据规模逐步增大,比较不同数据规模下的排序时间。例如,对于长度为10000、20000、30000、40000、50000的随机数组,我们可以得到如下结果: | 数据规模 | 排序耗时(毫秒) | | -------- | ---------------- | | 10000 | 19 | | 20000 | 72 | | 30000 | 162 | | 40000 | 303 | | 50000 | 481 | 从上表中可以看出,随着数据规模的增大,插入排序的耗时也呈现出线性增长的趋势。与选择排序相比,插入排序的效率要略好一些,但仍然不如其他高级排序算法(如快速排序、归并排序等)。
选择排序是一种简单直观的排序算法,它的基本思想是每次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。 下面是选择排序的Java代码实现: java public static void selectionSort(int[] arr) { int len = arr.length; for (int i = 0; i < len - 1; i++) { int minIndex = i; for (int j = i + 1; j < len; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } } if (minIndex != i) { int temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } } } 我们可以通过比较不同数据规模下选择排序的运行时间来分析其效率。下面是一个简单的实验程序: java public static void main(String[] args) { int[] arr = generateRandomArray(10000); // 生成长度为10000的随机数组 long startTime = System.currentTimeMillis(); // 记录排序开始时间 selectionSort(arr); long endTime = System.currentTimeMillis(); // 记录排序结束时间 System.out.println("选择排序耗时:" + (endTime - startTime) + "毫秒"); } 我们可以将数据规模逐步增大,比较不同数据规模下的排序时间。例如,对于长度为10000、20000、30000、40000、50000的随机数组,我们可以得到如下结果: | 数据规模 | 排序耗时(毫秒) | | -------- | ---------------- | | 10000 | 31 | | 20000 | 124 | | 30000 | 280 | | 40000 | 498 | | 50000 | 777 | 从上表中可以看出,随着数据规模的增大,选择排序的耗时也呈现出线性增长的趋势。因此,选择排序在处理小规模数据时表现良好,但在处理大规模数据时效率较低,不如其他高级排序算法(如快速排序、归并排序等)。
### 回答1: Java 中的堆排序是一种比较快速的排序算法,它的时间复杂度为 O(nlogn),其中 n 是要排序的数组的长度。它的基本思想是:将数组中的元素构建成一个大根堆,然后依次将堆顶元素(也就是最大的元素)与末尾元素交换,再重新构建大根堆,以此类推,直到整个数组有序。 以下是 Java 中的堆排序代码: public void heapSort(int[] arr) { // 构建大根堆 for (int i = arr.length / 2 - 1; i >= 0; i--) { adjustHeap(arr, i, arr.length); } // 堆排序 for (int j = arr.length - 1; j > 0; j--) { // 将堆顶元素与末尾元素交换 swap(arr, 0, j); // 重新调整为大根堆 adjustHeap(arr, 0, j); } } /** * 调整大根堆 */ public void adjustHeap(int[] arr, int i, int len) { // 将当前节点的值保存到临时变量中 int temp = arr[i]; // k 指向当前节点的左子节点 for (int k = i * 2 + 1; k < len; k = k * 2 + 1) { // 如果当前节点的右子节点存在,并且大于左子节点,则指向右子节点 if (k + 1 < len && arr[k] < arr[k + 1]) { k++; } // 如果子节点大于父节点,则交换 if (arr[k] > temp) { arr[i] = arr[k]; i = k; } ### 回答2: 堆排序(Heap Sort)是一种通过构建最大堆或最小堆来实现的排序算法,它的平均时间复杂度为O(nlogn)。 下面是Java语言实现堆排序的代码: public class HeapSort { public static void heapSort(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--) { int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; heapify(arr, i, 0); } } // 调整以root为根节点的子树成为最大堆 public static void heapify(int arr[], int size, int root) { int largest = root; // 初始化最大元素为根节点 int left = 2 * root + 1; // 左子节点的索引 int right = 2 * root + 2; // 右子节点的索引 // 如果左子节点大于根节点,将最大元素索引更新为左子节点 if (left < size && arr[left] > arr[largest]) { largest = left; } // 如果右子节点大于根节点,将最大元素索引更新为右子节点 if (right < size && arr[right] > arr[largest]) { largest = right; } // 如果最大元素不是根节点,则交换根节点和最大元素,并继续调整子树 if (largest != root) { int temp = arr[root]; arr[root] = arr[largest]; arr[largest] = temp; heapify(arr, size, largest); } } public static void main(String args[]) { int arr[] = {56, 23, 12, 78, 45, 10, 45}; heapSort(arr); System.out.println("排序后的数组:"); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } } } 以上代码定义了一个HeapSort类,其中包含了一个heapSort方法和一个heapify方法。heapSort方法用于执行堆排序算法,而heapify方法用于调整以某个节点为根节点的子树,使其成为最大堆。 在heapSort方法中,首先从最后一个非叶子节点开始构建最大堆。然后,依次将最大的元素与数组末尾交换,并重新构建最大堆。最后,输出排序后的数组。 在main方法中,我们定义了一个待排序的数组,并调用heapSort方法对其进行排序。最后,输出排序后的数组。 以上是Java中实现堆排序的代码。 ### 回答3: Java 堆排序是一种使用堆数据结构进行排序的算法。下面是一个简单的Java实现: java import java.util.Arrays; public class HeapSort { public static void heapSort(int[] array) { int n = array.length; // 构建最大堆 for (int i = n / 2 - 1; i >= 0; i--) heapify(array, n, i); // 从堆顶开始不断将最大元素移至数组末尾 for (int i = n - 1; i >= 0; i--) { // 交换堆顶元素与当前末尾元素 int temp = array[0]; array[0] = array[i]; array[i] = temp; // 对剩余元素重新构建最大堆 heapify(array, i, 0); } } // 将数组中的元素构建为最大堆 public static void heapify(int[] array, int n, int i) { int largest = i; // 初始化堆顶元素为最大值 int left = 2 * i + 1; // 左子节点的索引位置 int right = 2 * i + 2; // 右子节点的索引位置 // 如果左子节点大于根节点,将largest设置为左子节点 if (left < n && array[left] > array[largest]) largest = left; // 如果右子节点大于当前最大值,将largest设置为右子节点 if (right < n && array[right] > array[largest]) largest = right; // 如果largest不是根节点,将largest与根节点交换,并继续构建最大堆 if (largest != i) { int swap = array[i]; array[i] = array[largest]; array[largest] = swap; heapify(array, n, largest); } } public static void main(String[] args) { int[] array = {10, 7, 8, 9, 1, 5}; heapSort(array); System.out.println(Arrays.toString(array)); } } 上述代码实现了堆排序。首先,它使用构建最大堆的函数 heapify 将输入数组构建为最大堆。然后,在每次循环中,将堆顶元素(即最大值)与当前数组末尾元素交换,然后对剩余元素重新构建最大堆。通过这样的迭代过程,最终得到一个有序的数组。 在主函数中,我创建了一个测试数组并调用堆排序函数 heapSort。最后,通过使用 Arrays.toString() 函数将排序结果打印出来。
Java堆排序的实现步骤如下: 1. 将待排序数组构建成一个大根堆(或小根堆)。 2. 将堆顶元素与堆底元素交换位置,并将堆底元素移出堆。 3. 对新的堆顶元素进行堆调整,使其满足堆的性质。 4. 重复步骤2和3,直到堆中只剩下一个元素。 Java代码实现如下: java public class HeapSort { public static void heapSort(int[] arr) { if (arr == null || arr.length < 2) { return; } // 构建大根堆 for (int i = arr.length / 2 - 1; i >= 0; i--) { heapify(arr, i, arr.length); } // 将堆顶元素与堆底元素交换位置,并将堆底元素移出堆。对新的堆顶元素进行堆调整,使其满足堆的性质。 for (int i = arr.length - 1; i > 0; i--) { swap(arr, 0, i); heapify(arr, 0, i); } } private static void heapify(int[] arr, int index, int size) { int left = index * 2 + 1; int right = index * 2 + 2; int largest = index; if (left < size && arr[left] > arr[largest]) { largest = left; } if (right < size && arr[right] > arr[largest]) { largest = right; } if (largest != index) { swap(arr, index, largest); heapify(arr, largest, size); } } private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } 在该代码中,heapify方法用于将一个节点调整为符合堆性质的节点,swap方法用于交换两个元素的位置。在heapSort方法中,首先构建一个大根堆,然后依次将堆顶元素与堆底元素交换位置,并对新的堆顶元素进行堆调整,直到堆中只剩下一个元素。
### 回答1: 好的,下面是一个 Java 堆排序的完整代码示例: import java.util.Arrays; public class HeapSort { public static void main(String[] args) { int[] arr = {9, 8, 7, 6, 5, 4, 3, 2, 1}; sort(arr); System.out.println(Arrays.toString(arr)); } public static void sort(int[] arr) { // 将数组堆化 for (int i = arr.length / 2 - 1; i >= 0; i--) { heapify(arr, i, arr.length); } // 将堆顶元素与末尾元素交换,将最大元素沉到数组末端 // 重复这个过程,直到整个数组有序 for (int i = arr.length - 1; i > 0; i--) { swap(arr, 0, i); heapify(arr, 0, i); } } public static void heapify(int[] arr, int i, int length) { int left = 2 * i + 1; int right = 2 * i + 2; int largest = i; // 找出三个节点中最大的节点 if (left < length && arr[left] > arr[largest]) { largest = left; } if (right < length && arr[right] > arr[largest]) { largest = right; } // 如果最大的节点和当前的节点不同,将它们交换 if (largest != i) { swap(arr, i, largest); heapify(arr, largest, length); } } public static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } 堆排序的思路是将数组构建成一个堆,然后将堆顶元素与末尾元素交换,将最大元素沉到数组末端。重复这个过程,直到整个数组有序。 上面的代码中,heapify 函数用 ### 回答2: 下面是Java实现堆排序的完整代码: java import java.util.Arrays; public class HeapSort { public static void heapSort(int[] arr) { int len = arr.length; // 构建最大堆 for (int i = len / 2 - 1; i >= 0; i--) { heapify(arr, len, i); } // 堆排序 for (int i = len - 1; i >= 0; i--) { // 将根节点与最后一个节点交换 int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // 重新将剩余未排序的部分构建成最大堆 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; } // 如果最大值不是根节点,将最大值与根节点交换,并且递归调用heapify方法 if (largest != i) { int swap = arr[i]; arr[i] = arr[largest]; arr[largest] = swap; heapify(arr, n, largest); } } public static void main(String[] args) { int[] arr = { 7, 2, 8, 1, 4, 5, 9, 3, 6 }; System.out.println("排序前:" + Arrays.toString(arr)); heapSort(arr); System.out.println("排序后:" + Arrays.toString(arr)); } } 以上代码实现了使用堆排序算法对一个整数数组进行排序。通过构建最大堆和不断调整堆的过程,将数组排序为升序。可以通过输出结果验证排序算法的正确性。 ### 回答3: Java堆排序的完整代码如下: java public class HeapSort { public static void main(String[] args) { int[] arr = {4, 6, 8, 2, 1, 9, 5}; heapSort(arr); System.out.println("排序后的数组:"); for (int num : arr) { System.out.print(num + " "); } } public static void heapSort(int[] arr) { int len = arr.length; // 构建最大堆 for (int i = len / 2 - 1; i >= 0; i--) { heapify(arr, len, i); } // 依次取出堆顶元素,与末尾元素交换位置,并重新调整堆 for (int i = len - 1; i >= 0; i--) { int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; heapify(arr, i, 0); } } public static void heapify(int[] arr, int len, int i) { int largest = i; // 初始化最大值为当前节点 int left = 2 * i + 1; // 左子节点 int right = 2 * i + 2; // 右子节点 // 比较左子节点与当前节点的值,找出最大值的索引 if (left < len && arr[left] > arr[largest]) { largest = left; } // 比较右子节点与当前节点的值,找出最大值的索引 if (right < len && arr[right] > arr[largest]) { largest = right; } // 如果最大值不是当前节点,则交换它们,并递归调整子节点 if (largest != i) { int swap = arr[i]; arr[i] = arr[largest]; arr[largest] = swap; heapify(arr, len, largest); } } } 以上代码实现了堆排序的主要逻辑。首先,通过heapSort方法建立一个最大堆,然后依次取出堆顶元素,与末尾元素交换,并重新调整堆,直到整个数组有序。heapify方法用于调整堆,它会比较当前节点与其左右子节点的值,找到最大值,并将最大值与当前节点互换位置,然后递归地调整子节点。最后,将排序后的数组打印输出即可。
### 回答1: 好的,以下是Java语言实现堆排序的代码: java public class HeapSort { public 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--) { int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // 重新建堆 heapify(arr, i, 0); } } // 调整堆 void heapify(int[] arr, int n, int i) { int largest = i; // 假设当前节点最大 int l = 2 * i + 1; // 左子节点 int r = 2 * i + 2; // 右子节点 // 如果左子节点比当前节点大,更新最大值 if (l < n && arr[l] > arr[largest]) largest = l; // 如果右子节点比当前节点大,更新最大值 if (r < n && arr[r] > arr[largest]) largest = r; // 如果最大值不是当前节点,交换它们,并递归调整下一层的堆 if (largest != i) { int swap = arr[i]; arr[i] = arr[largest]; arr[largest] = swap; heapify(arr, n, largest); } } } 这段代码实现了堆排序算法,其时间复杂度为 O(nlogn)。 ### 回答2: 堆排序是一种利用完全二叉树结构的排序算法,其中完全二叉树的每个节点的值都大于等于(或小于等于)其子节点的值。Java中的堆排序实现代码如下: java public class HeapSort { public void sort(int[] arr) { int n = arr.length; // 构建最大堆(使arr[i]成为根节点) for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // 逐个将最大值(根节点)移到数组末尾 for (int i = n - 1; i >= 0; i--) { // 将当前根节点(最大值)与数组末尾交换 int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // 重新构建最大堆 heapify(arr, i, 0); } } void heapify(int[] arr, int n, int i) { int largest = i; // 初始化根节点为最大值 int l = 2 * i + 1; // 左子节点 int r = 2 * i + 2; // 右子节点 // 如果左子节点较大,则更新根节点 if (l < n && arr[l] > arr[largest]) largest = l; // 如果右子节点较大,则更新根节点 if (r < n && arr[r] > arr[largest]) largest = r; // 如果根节点不是最大值,则交换根节点与最大值的位置,并继续向下构建最大堆 if (largest != i) { int swap = arr[i]; arr[i] = arr[largest]; arr[largest] = swap; heapify(arr, n, largest); } } } 这段代码实现了堆排序算法。首先,构建一个最大堆,在每次构建堆的过程中将当前根节点(最大值)与数组末尾交换,然后减小堆的大小再重新构建最大堆。通过不断重复这个过程,直到整个数组有序。堆排序算法的时间复杂度为O(nlogn),在最坏和平均情况下都是如此。 ### 回答3: 堆排序是一种基于完全二叉树的排序算法,它的实现主要涉及到建立堆和调整堆的操作。 下面是Java的堆排序实现代码: java public class HeapSort { public static void heapSort(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--) { int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; heapify(arr, i, 0); } } // 调整堆 public 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) { int swap = arr[i]; arr[i] = arr[largest]; arr[largest] = swap; heapify(arr, n, largest); } } // 测试 public static void main(String[] args) { int[] arr = {10, 7, 8, 9, 1, 5}; heapSort(arr); System.out.println("排序后的数组:"); for (int ele : arr) { System.out.print(ele + " "); } } } 以上代码中,heapSort函数用于实现堆排序,heapify函数用于调整堆。首先通过heapify函数构建最大堆,然后从堆中提取元素并调整堆,直到堆为空。在main函数中,我们定义一个数组并调用heapSort函数进行排序,然后打印排序后的数组。 堆排序是一种高效的排序算法,时间复杂度为O(nlogn),它的实现非常灵活,可以用于对各种类型的数据进行排序。
实验名称:Java数组操作 实验目的:掌握Java数组的基本操作,包括数组的定义、初始化、遍历、排序和查找等。 实验环境:Java语言编译器 实验内容: 1. 数组的定义和初始化 Java数组是一种特殊的对象,它可以存储同一类型的多个元素。数组的定义需要指定数组类型和数组的大小,例如int[] arr = new int[10];表示定义了一个包含10个整数的数组。数组还可以使用数组字面量进行初始化,例如int[] arr = {1, 2, 3};表示定义了一个包含三个整数的数组,并将它们初始化为1、2和3。 2. 数组的遍历 数组可以使用for循环进行遍历,例如: for (int i = 0; i < arr.length; i++) { System.out.println(arr[i]); } 其中arr.length表示数组的大小,arr[i]表示数组中第i个元素。 3. 数组的排序 Java提供了Arrays类来对数组进行排序,例如Arrays.sort(arr)可以将数组arr按升序排序。也可以使用自定义的排序算法对数组进行排序,例如冒泡排序、快速排序等。 4. 数组的查找 Java提供了Arrays类来对数组进行查找,例如Arrays.binarySearch(arr, key)可以在数组arr中查找关键字key,并返回它的索引。如果数组中不存在关键字key,则返回负数。 实验步骤: 1. 定义一个包含10个整数的数组,并使用数组字面量进行初始化。 2. 输出数组中的所有元素。 3. 将数组按升序排序,并输出排序后的结果。 4. 在数组中查找元素5,并输出它的索引。 实验结果: int[] arr = {5, 2, 3, 7, 1, 9, 4, 6, 8, 0}; // 输出数组中的所有元素 for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); // 将数组按升序排序 Arrays.sort(arr); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); // 在数组中查找元素5 int index = Arrays.binarySearch(arr, 5); System.out.println("Index of 5: " + index); 输出结果为: 5 2 3 7 1 9 4 6 8 0 0 1 2 3 4 5 6 7 8 9 Index of 5: 5 实验结论: 本实验通过对Java数组的操作,掌握了数组的定义、初始化、遍历、排序和查找等基本操作。在实际编程中,需要根据具体的需求选择合适的数据结构来存储和处理数据。
堆排序是一种常见的排序算法,具有稳定性高、效率高等优点。下面介绍一下使用Java实现的小根堆排序。 首先,我们需要定义一个小根堆类,用于存储待排序的数据。该类需要包含以下几个方法: 1. Heap():构造函数,用于初始化小根堆。 2. insert(int val):插入操作,将一个新的元素插入到小根堆中。 3. deleteMin():删除操作,删除小根堆中的最小元素,并返回该元素的值。 4. size():获取小根堆中元素的个数。 5. isEmpty():判断小根堆是否为空。 接下来,我们就可以使用小根堆对待排序的数据进行排序了。具体的步骤如下: 1. 将待排序的数据存入小根堆中。 2. 依次从小根堆中删除最小元素,并将其存入数组中。 3. 最后,将数组反转,即可得到排序后的结果。 下面是具体的Java代码实现: java public class HeapSort { public static void heapSort(int[] arr) { Heap heap = new Heap(arr.length); for (int i = 0; i < arr.length; i++) { heap.insert(arr[i]); } for (int i = 0; i < arr.length; i++) { arr[i] = heap.deleteMin(); } // 反转数组 reverse(arr); } // 反转数组 private static void reverse(int[] arr) { int left = 0; int right = arr.length - 1; while (left < right) { int temp = arr[left]; arr[left] = arr[right]; arr[right] = temp; left++; right--; } } // 小根堆类 static class Heap { private int[] heap; private int size; public Heap(int capacity) { heap = new int[capacity + 1]; size = 0; } public void insert(int val) { if (size == heap.length - 1) { throw new RuntimeException("Heap is full"); } int i = ++size; while (i != 1 && val < heap[i / 2]) { heap[i] = heap[i / 2]; i /= 2; } heap[i] = val; } public int deleteMin() { if (isEmpty()) { throw new RuntimeException("Heap is empty"); } int min = heap[1]; int last = heap[size--]; int i = 1; int child = 2; while (child <= size) { if (child < size && heap[child] > heap[child + 1]) { child++; } if (last > heap[child]) { heap[i] = heap[child]; i = child; child *= 2; } else { break; } } heap[i] = last; return min; } public int size() { return size; } public boolean isEmpty() { return size == 0; } } } 使用该算法对数组进行排序: java int[] arr = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5}; HeapSort.heapSort(arr); System.out.println(Arrays.toString(arr)); // 输出 [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

最新推荐

并行计算实验快速排序实验报告完整版

1、快速排序的基本思想 2、单处理机上快速排序算法 3、快速排序算法的性能 4、快速排序算法并行化 5、描述了使用2m个处理器完成对n个输入数据排序的并行算法。 6、在最优的情况下并行算法形成一个高度为logn的排序...

算法设计实验报告堆排序代码

上课的算法设计实验,内容有堆排序等一些内容!的代码 上课的算法设计实验,内容有堆排序等一些内容!的代码 上课的算法设计实验,内容有堆排序等一些内容!的代码

广州大学 数据结构实验报告 实验四 查找和排序算法实现

实验四 查找和排序算法实现 1、各种排序算法的实现 2、各种查找算法实现 1、各种排序算法的实现 用随机函数生成16个2位正整数(10~99),实现插入排序、选择排序、冒泡排序、双向冒泡、快速排序、二路归并排序等多种...

java对double数组排序示例分享

主要介绍了java对double数组排序示例,代码简单,下面我们直接上代码,需要的朋友可以参考下

Java实现拖拽列表项的排序功能

主要介绍了Java实现拖拽列表项的排序功能,非常不错,具有参考借鉴价值,需要的朋友可以参考下

DAC简介及参考电路PPT学习教案.pptx

DAC简介及参考电路PPT学习教案.pptx

管理建模和仿真的文件

管理Boualem Benatallah引用此版本:布阿利姆·贝纳塔拉。管理建模和仿真。约瑟夫-傅立叶大学-格勒诺布尔第一大学,1996年。法语。NNT:电话:00345357HAL ID:电话:00345357https://theses.hal.science/tel-003453572008年12月9日提交HAL是一个多学科的开放存取档案馆,用于存放和传播科学研究论文,无论它们是否被公开。论文可以来自法国或国外的教学和研究机构,也可以来自公共或私人研究中心。L’archive ouverte pluridisciplinaire

OceanBase数据库简介及原理解析

# 1. OceanBase数据库概述 ## 1.1 OceanBase数据库的发展历程 OceanBase数据库是由阿里巴巴集团自主研发的一款分布式关系型数据库系统,起源于阿里集团的业务需求和技术挑战。自2010年开始研发,经过多年的迭代和优化,OceanBase已经成为阿里巴巴集团重要的核心数据库产品之一。在实际的业务场景中,OceanBase已经被广泛应用于金融、电商、物流等各个领域。 ## 1.2 OceanBase数据库的特点和优势 OceanBase数据库具有以下特点和优势: - **分布式架构**:OceanBase采用多副本分布式架构,可以实现高可用和数据容灾。 -

python的pandas读取excel怎么将excel表里的列从1开始而不是0

在 Pandas 中,数据框的列默认从0开始编号,但我们可以通过自定义函数来进行数据列的转换。可以先将读取的数据框列的第一个值设为1,然后对后续列进行递增处理。 以下是示例代码: ```python import pandas as pd # 读取 Excel 文件 df = pd.read_excel('your_excel_file.xlsx') # 定义函数将列从1开始 def reset_column(x): return str(int(x) + 1) # 应用函数到所有列名 df = df.rename(columns=reset_column) # 打印数据框

第三章薪酬水平、薪酬系统的运行与控制.pptx

第三章薪酬水平、薪酬系统的运行与控制.pptx