济南建网站多少钱,速成网站怎么做,网站策划建设方案书,网站模板安装好后Java手写堆排序#xff08;Heap Sort#xff09;
1. 思维导图
下面是使用Mermaid代码绘制的思维导图#xff0c;用于解释堆排序算法的实现思路原理#xff1a; #mermaid-svg-cFIgsLSm5LOBm5Gl {font-family:trebuchet ms,verdana,arial,sans-serif;font-size…Java手写堆排序Heap Sort
1. 思维导图
下面是使用Mermaid代码绘制的思维导图用于解释堆排序算法的实现思路原理 #mermaid-svg-cFIgsLSm5LOBm5Gl {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-cFIgsLSm5LOBm5Gl .error-icon{fill:#552222;}#mermaid-svg-cFIgsLSm5LOBm5Gl .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-cFIgsLSm5LOBm5Gl .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-cFIgsLSm5LOBm5Gl .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-cFIgsLSm5LOBm5Gl .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-cFIgsLSm5LOBm5Gl .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-cFIgsLSm5LOBm5Gl .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-cFIgsLSm5LOBm5Gl .marker{fill:#333333;stroke:#333333;}#mermaid-svg-cFIgsLSm5LOBm5Gl .marker.cross{stroke:#333333;}#mermaid-svg-cFIgsLSm5LOBm5Gl svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-cFIgsLSm5LOBm5Gl .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-cFIgsLSm5LOBm5Gl .cluster-label text{fill:#333;}#mermaid-svg-cFIgsLSm5LOBm5Gl .cluster-label span{color:#333;}#mermaid-svg-cFIgsLSm5LOBm5Gl .label text,#mermaid-svg-cFIgsLSm5LOBm5Gl span{fill:#333;color:#333;}#mermaid-svg-cFIgsLSm5LOBm5Gl .node rect,#mermaid-svg-cFIgsLSm5LOBm5Gl .node circle,#mermaid-svg-cFIgsLSm5LOBm5Gl .node ellipse,#mermaid-svg-cFIgsLSm5LOBm5Gl .node polygon,#mermaid-svg-cFIgsLSm5LOBm5Gl .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-cFIgsLSm5LOBm5Gl .node .label{text-align:center;}#mermaid-svg-cFIgsLSm5LOBm5Gl .node.clickable{cursor:pointer;}#mermaid-svg-cFIgsLSm5LOBm5Gl .arrowheadPath{fill:#333333;}#mermaid-svg-cFIgsLSm5LOBm5Gl .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-cFIgsLSm5LOBm5Gl .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-cFIgsLSm5LOBm5Gl .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-cFIgsLSm5LOBm5Gl .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-cFIgsLSm5LOBm5Gl .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-cFIgsLSm5LOBm5Gl .cluster text{fill:#333;}#mermaid-svg-cFIgsLSm5LOBm5Gl .cluster span{color:#333;}#mermaid-svg-cFIgsLSm5LOBm5Gl div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-cFIgsLSm5LOBm5Gl :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 是 否 建立最大堆 交换堆顶和最后一个元素 维护最大堆性质 是否完成排序? 结束 2. 手写堆排序的必要性
堆排序是一种高效的排序算法它的时间复杂度为O(nlogn)具有以下几个方面的优势
相对于其他基于比较的排序算法如快速排序、归并排序堆排序是一种原地排序算法不需要额外的辅助空间堆排序是稳定的排序算法不会改变相同元素之间的顺序堆排序在最坏情况下仍具有较好的性能因此在一些对排序稳定性要求较高的场景中堆排序是一个不错的选择。
3. 市场调研
据市场调研堆排序在实际应用中广泛使用特别是在以下场景中
大规模数据的排序由于堆排序的时间复杂度较低且具备稳定性因此在需要对大规模数据进行排序的场景中堆排序是一种常用的选择优先级队列堆排序的基础是堆这种数据结构而堆被广泛用于实现优先级队列。优先级队列是一种可以动态地插入和删除元素并且每次操作都能高效地找到最大或最小值的数据结构而堆正是实现这一特性的关键排名统计堆排序在一些需要对数据进行排名统计的场景中也有应用例如按照成绩对学生进行排名、按照销售额对商品进行排名等。
4. 实现步骤
堆排序的实现步骤包括以下几个部分
4.1 建立最大堆
首先我们需要构建一个最大堆以便后续的排序操作。建立最大堆的步骤如下
从最底层的非叶子节点开始逐层向上调整使得每个节点都满足最大堆的性质对于当前节点比较其与左右子节点的大小如果存在比当前节点更大的子节点则交换两者的位置重复上述比较和交换的步骤直到当前节点满足最大堆的性质或成为叶子节点。
以下是建立最大堆的Java代码
// 建立最大堆
public static void buildMaxHeap(int[] array, int length) {for (int i length / 2 - 1; i 0; i--) {heapify(array, length, i);}
}4.2 交换堆顶和最后一个元素
建立最大堆之后最大堆的堆顶元素即为数组中的最大值。我们将堆顶元素与数组中的最后一个元素进行交换。
以下是交换堆顶和最后一个元素的Java代码
// 交换堆顶和最后一个元素
public static void swap(int[] array, int i, int j) {int temp array[i];array[i] array[j];array[j] temp;
}4.3 维护最大当交换堆顶和最后一个元素后我们需要维护最大堆的性质以保证新的堆顶元素是剩下元素中的最大值。
维护最大堆的步骤如下
将交换后的堆顶元素原数组的最后一个元素下沉到合适的位置以满足最大堆的性质每次将当前节点与其子节点进行比较如果存在比当前节点更大的子节点则将其与其中较大的子节点进行交换重复上述比较和交换的步骤直到当前节点满足最大堆的性质或成为叶子节点。
以下是维护最大堆的Java代码
// 维护最大堆性质
public static void heapify(int[] array, int length, int i) {int largest i; // 当前节点int left 2 * i 1; // 左子节点int right 2 * i 2; // 右子节点// 如果左子节点比当前节点大if (left length array[left] array[largest]) {largest left;}// 如果右子节点比当前节点大if (right length array[right] array[largest]) {largest right;}// 如果最大值不是当前节点交换它们的位置并继续调整if (largest ! i) {swap(array, i, largest);heapify(array, length, largest);}
}4.4 排序
在建立最大堆和维护最大堆的基础上我们可以进行堆排序了。
堆排序的步骤如下
通过调用建立最大堆的函数构建一个最大堆从最后一个元素开始依次将堆顶元素与当前元素进行交换并缩小堆的范围以排除已排序的元素重复上述交换和缩小堆范围的操作直到只剩下一个元素。
以下是堆排序的Java代码
// 堆排序
public static void heapSort(int[] array) {int length array.length;// 建立最大堆buildMaxHeap(array, length);// 从最后一个元素开始依次交换堆顶和当前元素并调整堆for (int i length - 1; i 0; i--) {swap(array, 0, i);heapify(array, i, 0);}
}5. 手写总结
堆排序是一种高效稳定的排序算法适用于大规模数据的排序和优先级队列的实现。它的实现步骤包括建立最大堆、交换堆顶和最后一个元素、维护最大堆性质以及排序操作。通过合理地利用最大堆的性质堆排序能够在O(nlogn)的时间复杂度下完成排序任务。
6. 拓展案例代码
按照成绩对学生进行排名
假设有一个学生列表每个学生包含姓名和成绩两个属性。我们可以使用堆排序按照成绩对学生进行排名。
class Student {String name;int score;// 构造函数和其他方法省略...
}public static void heapSortByScore(Student[] students) {int length students.length;// 建立最大堆按照成绩进行比较buildMaxHeapByScore(students, length);// 从最后一个学生开始依次交换堆顶和当前学生并调整堆for (java
int i length - 1; i 0; i--) {swap(students, 0, i);heapifyByScore(students, i, 0);}
}// 建立最大堆按照成绩进行比较
public static void buildMaxHeapByScore(Student[] students, int length) {for (int i length / 2 - 1; i 0; i--) {heapifyByScore(students, length, i);}
}// 维护最大堆性质按照成绩进行比较
public static void heapifyByScore(Student[] students, int length, int i) {int largest i;int left 2 * i 1;int right 2 * i 2;if (left length students[left].score students[largest].score) {largest left;}if (right length students[right].score students[largest].score) {largest right;}if (largest ! i) {swap(students, i, largest);heapifyByScore(students, length, largest);}
}// 交换两个学生的位置
public static void swap(Student[] students, int i, int j) {Student temp students[i];students[i] students[j];students[j] temp;
}使用示例
Student[] students new Student[5];
students[0] new Student(Alice, 80);
students[1] new Student(Bob, 75);
students[2] new Student(Charlie, 90);
students[3] new Student(David, 85);
students[4] new Student(Eve, 70);heapSortByScore(students);for (Student student : students) {System.out.println(student.name : student.score);
}输出结果
Charlie: 90
Alice: 80
David: 85
Bob: 75
Eve: 70按照成绩从高到低排名的结果就是Charlie、Alice、David、Bob、Eve。
这是一个基于堆排序的简单拓展案例可以根据具体需求进行进一步的扩展和优化。希望对你有帮助
