大家好，又见面了，我是你们的朋友全栈君。
堆排序理论：
https://blog.csdn.net/qq_36186690/article/details/82505569
代码：
package com.paixu.paixuTest;
import java.util.Arrays;
import java.util.Scanner;
/** * 选择排序 * 1）简单选择排序 * 2）堆排序 */
public class xuanZhePaiXu {
public static void main(String[] args) {
System.out.println("请输入带排序数，以空格间隔：");
Scanner scanner = new Scanner(System.in);
int[] arr = new int[5];
while (scanner.hasNext()) {
for (int i = 0; i < arr.length; i++) {
arr[i] = scanner.nextInt();
}
// 1、简单选择排序
jianDanZuanZhr(arr);
// 2、堆排序
duiPaiXu(arr);
}
}
/** * 堆排序 * @param arr * 堆满足两个条件 1）完全二叉树 2）父节点必须大于或者等于子节点，或者是小于等于 * 堆排序的过程： * 1）先将无序的序列构造成大顶堆或者小顶推（升序就构造大顶堆、降序就构造小顶堆） * 2）将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端; * 3）重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。 */
private static void duiPaiXu(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); // 交换元素后，又重新构造大顶堆
}
System.out.println("堆排序："+Arrays.toString(arr));
}
private static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
/** * 构造大顶推 * @param arr * @param i * @param length * 父亲：(i-1)/2 * 子节点：2i+1 2i+2 */
private static void adjustHeap(int[] arr, int i, int length) {
int temp = arr[i];
for (int k=i*2+1;k<length;k=i*2+1){
//从i结点的左子结点开始，也就是2i+1处开始
if (k+1<length && arr[k]<arr[k+1]){
//如果左子结点小于右子结点，k指向右子结点
k++;
}
if (arr[k]>temp){
//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
arr[i] = arr[k]; // 子节点的值赋值给了父节点，那么最后原本父节点的值也要给子节点
i = k; // 子节点的下标赋值给i，为了最后赋值
}else {
break;
}
}
arr[i] = temp;
}
/** 简单选择排序 * 每次从后面选择一个最小的与前面设置的最小的交换 * @param arr */
private static void jianDanZuanZhr(int[] arr) {
for (int i=0;i<arr.length-1;i++){
int min = i; // 初始化第一个最小
for (int j=i+1;j<arr.length;j++){
if (arr[j]<arr[min]){
min = j;
}
}
if (min!=i){
// 不等，说明有比他小的元素。
int temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
}
System.out.println("简单选择排序："+Arrays.toString(arr));
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/156958.html原文链接：https://javaforall.net
