选择排序-Java「建议收藏」

全栈程序员-站长 • 2022年7月8日下午1:16 • 未分类 • 阅读 24

大家好，又见面了，我是你们的朋友全栈君。

堆排序理论：

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));
    }
}