插入排序（学习笔记）

插入排序

每一轮插入排序后的结果与打扑克牌取牌原理相似，将取到的牌插入到合适的位置，但在程序实现方面还是基于交换的算法。
它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。
在这里插入图片描述

在这里插入图片描述

import java.util.Random;public class InsertSelect {public static void main(String[] args) {int[] arr = createArray(10);printArray(arr);//插入排序insertSort(arr);System.out.println("插入排序后的数组为：");printArray(arr);}public static void insertSort(int[] arr){if (arr == null || arr.length < 2){return;}for (int i = 1; i < arr.length; i++) {//0~i 做到有序for (int j = i-1;j>=0&&arr[j]>arr[j+1];j--){//j>=0 防止j--数组下标越界//不停的交换，直到0——i是有序的swap(arr,j,j+1);}}}//交换数组元素的方法public static void swap(int[] arr,int i,int j){//异或交换法——i和j是一个位置的话就会出错arr[i] = arr[i] ^ arr[j];arr[j] = arr[i] ^ arr[j];arr[i] = arr[i] ^ arr[j];//常规交换/* int temp = arr[i];arr[i] = arr[j];arr[j] = temp;*/}//随机生成数组，数组中的元素[0,20)public static int[] createArray(int length) {int[] arr = new int[length];Random random = new Random();for (int i = 0; i < arr.length; i++) {arr[i] = random.nextInt(20);//[0,20)}return arr;}//打印数组方法public static void printArray(int[] arr){for (int i=0;i<arr.length;i++) {if (i==0){if (arr.length==1){System.out.println("["+arr[0]+"]");}else{System.out.print("["+arr[i]+",");}}else if(i==arr.length-1){System.out.println(arr[i]+"]");}else {System.out.print(arr[i]+",");}}System.out.println("--------------------------------------------------------");}
}