算法学习（三）直接插入排序
2021-04-12 09:29
标签：while 直接 print test 数组 循环数组 插入 public 技术 今天学习第三种排序算法：直接插入排序，以前没怎么详细了解过，今天来看看图解一下~~ 基本思想：类似于我们玩扑克牌的时候，每抽一张牌就根据大小插入手中的场景；每次循环过程中，我们都选取一个元素去插入已经排序好的部分元素，最终排序完成~ 时间复杂度：O(n²) 图解： 参考资料： 算法学习（三）直接插入排序 标签：while 直接 print test 数组 循环数组 插入 public 技术 原文地址：https://www.cnblogs.com/riches/p/13257242.html一、引言
二、直接插入算法
插入算法工具类
/**
* 直接插入排序算法工具类
*/
public class ChaRuUtil {
/**
* 直接插入排序【对外暴露静态方法】
*/
public static void insertionSort(int[] arr) {
System.out.println("========排序前的数组，元素为：" + showItem(arr) + "========");
//1、定义变量
int value;//待插入元素
int index;//初始值为待插入元素前一个元素的索引
//2、循环数组进行插入
for (int i = 1; i ) {
//PS：i从第二个元素开始，我们默认第一个元素是有序的，循环条件是小于数组长度，因为也要将最后一个元素插入到前面的序列
value = arr[i];
index = i - 1;//初始为前一个元素
System.out.println("第【" + i + "】次排序时待插入元素为：" + value + " index初始化为：" + index);
//3、while循环,当插入元素比index对应的元素小时，index对应的元素向后移动一位，并使index自减1进行下次循环
while (index >= 0 && value arr[index]) {
//4、每当前面的元素比待插入元素大，就向后移动一个位置，这时候前面就会多出一个位置来插
arr[index + 1] = arr[index];
//5、index减少1以后，下次循环继续往前比较
index--;
}
//6、当退出循环，表明已经找到了待插入位置，即index + 1
arr[index + 1] = value;
System.out.println("第【" + i + "】次排序后的数组，元素为：" + showItem(arr) + "========");
System.out.println();
}
}
/**
* 返回数组字符串
*/
public static String showItem(int[] arr) {
String itemStr = "";
if (null != arr) {
itemStr = "【 ";
for (int item : arr) {
itemStr = itemStr + " " + item;
}
itemStr += " 】";
}
return itemStr;
}
}
测试类
/**
* 直接插入排序工具测试类
*/
public class ChaRuTest {
public static void main(String[] args) {
//1、设置乱序数组
int[] arr = {1, 8, 3, 6, 9, 4, 5};
//2、调用直接插入排序工具类
ChaRuUtil.insertionSort(arr);
}
}
解析
