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

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

堆排序理论：

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