插入排序
- 概述
- 步骤
- 代码示例
- 输出结果
概述
插入排序是一种最简单直观的排序算法，它的工作原理是通过创建有序序列和无序序列，然后再遍历无序序列得到里面每一个数字，把每一个数字插入到有序序列中正确的位置。
插入排序是一种简单直观的排序算法，其基本思想是将未排序的元素逐个插入到已排序序列中的正确位置，从而构建有序的序列。
插入排序在插入的时候，有优化算法，在遍历有序序列找正确位置时，可以采取二分查找
插入排序的时间复杂度为 O(n^2)，但是在处理小型数组或基本有序的数组时，插入排序的性能往往比其他复杂的排序算法更好。此外，插入排序是稳定的排序算法，即具有相等值的元素在排序后的相对位置不会改变。
步骤
插入排序的过程如下：
-
从第一个元素开始，认为该元素已经是有序序列。
-
取出下一个元素，将其与已排序的元素从右到左依次比较。
-
如果已排序的元素大于当前元素，则将已排序的元素后移一位，继续比较前一个已排序的元素。
-
重复步骤 3，直到找到一个已排序的元素小于或等于当前元素，或者到达已排序序列的起始位置。
-
将当前元素插入到已排序序列中找到的位置后面。
-
重复步骤 2 到 5，直到所有元素都被插入到有序序列中。
插入排序每次将一个元素插入到已排序序列中，并将该元素放置在正确的位置上。通过逐步扩大已排序的部分，最终完成整个数组的排序。
将0索引的元素到N索引的元素看做是有序的，把N+1索引的元素到最后一个当成是无序的。遍历无序的数据，将遍历到的元素插入有序序列中适当的位置，如遇到相同数据，插在后面。
N的范围：0~最大索引
代码示例
需求：采用插入排序将下列数据进行排序，数据如下{3, 23, 36, 37, 40, 43, 44, 38, 5, 47, 15, 47, 36, 26, 27, 2, 46, 4, 19, 23, 50, 23, 48};
例如：
package text.text02;
/*
插入排序：
插入排序是一种最简单直观的排序算法，它的工作原理是通过创建有序序列和无序序列，然后再遍历无序序列得到里面每一个数字，把每一个数字插入到有序序列中正确的位置。
插入排序在插入的时候，有优化算法，在遍历有序序列找正确位置时，可以采取二分查找
*/
public class text13A {
public static void main(String[] args) {
int[] arr = {3, 23, 36, 37, 40, 43, 44, 38, 5, 47, 15, 47, 36, 26, 27, 2, 46, 4, 19, 23, 50, 23, 48};
//定义一个变量记录无序序列的起始索引
int startIndex = -1;
//遍历数组，找到无序序列的起始索引
for (int i = 0; i < arr.length - 1; i++) {
//表明前i-1个数和第i+1个数都小于第i个数，说明前i个数都是有序的，第i+1个数以后都是无序的
if (arr[i] > arr[i + 1]) {
//将无序序列的起始索引赋值给startIndex
startIndex = i + 1;
break;
}
}
//调用method1方法遍历数组，将无序序列中的数据插入到有序序列中(顺序查找/基本查找)
int[] arr1 = method1(arr, startIndex);
//调用method2方法遍历数组，将无序序列中的数据插入到有序序列中(折半查找/二分查找)
int[] arr2 = method2(arr, startIndex);
//调用printfArray方法遍历输出数组数据
System.out.println("这是基本查找/顺序查找的方法：");
printfArray(arr1); //2 3 4 5 15 19 23 23 23 26 27 36 36 37 38 40 43 44 46 47 47 48 50
System.out.println(); //换行
System.out.println("这是折半查找/二分查找的方法：");
printfArray(arr2); //2 3 4 5 15 19 23 23 23 26 27 36 36 37 38 40 43 44 46 47 47 48 50
}
//遍历数组方法1，将无序序列中的数据插入到有序序列中(顺序查找/基本查找)
public static int[] method1(int[] arr, int startIndex) {
for (int i = startIndex; i < arr.length; i++) {
//定义一个变量记录i的值（因为后面要更改j的值（j--），如果直接更改i，则循环永远不到达到i < arr.length）
int j = i;
while (j > 0 && arr[j - 1] > arr[j]) { //j表示无序序列的其实索引，j-1表示有序序列的最后索引
//交换数据
int temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
j--;
}
}
return arr;
}
//遍历数组方法2，将无序序列中的数据插入到有序序列中(折半查找/二分查找)
public static int[] method2(int[] arr, int startIndex) {
//利用循环交换数组元素进行排序
for (int i = startIndex; i < arr.length; i++) {
//调用judgeIndex方法获取要插入元素的位置
int index = judgeIndex(arr, i);
//定义一个变量记录要插入的数
int number = arr[i];
//利用循环将已排序部分中要插入位置之后的元素向右移动，为待插入元素腾出空间（从 i1 开始向左遍历，将每个元素向右移动一位，直到达到插入位置 index。）
for (int i1 = i; i1 > index; i1--) {
arr[i1] = arr[i1 - 1];
}
//将记录要插入的值的变量赋值给要插入的位置
arr[index] = number;
}
return arr;
}
//定义方法用来判断要插入的数的位置
public static int judgeIndex(int[] arr, int startIndex) {
//定义变量记录已经排序的数中的起始索引
int min = 0;
//定义变量记录已经排序的数中的结束索引
int max = startIndex - 1;
//利用循环找到要插入的位置
while (min <= max) {
//获取已排序的数的中间索引
int mid = (min + max) / 2;
//如果中间索引所对应的数等于要插入得数
if (arr[mid] == arr[startIndex]) {
return mid;
}
//如果中间索引所对应的数小于要插入得数
if (arr[mid] < arr[startIndex]) {
min = mid + 1;
}
//如果中间索引所对应的数大于要插入得数
if (arr[mid] > arr[startIndex]) {
max = mid - 1;
}
}
//当循环结束时，“min” 指针指向了插入位置的右侧。在每次二分查找的过程中，如果目标元素小于当前中间元素，那么 “max” 指针会更新为 “mid - 1”，如果目标元素大于当前中间元素，那么 “min” 指针会更新为 “mid + 1”。最终当满足 “min > max” 时，说明目标元素应该插入的位置就是 “min” 指向的位置。因此，当二分查找未找到目标元素时，插入位置就是 “min” 所指向的位置，所以返回 “min”。如果找到目标元素，那么也返回该元素在数组中的位置。
return min;
}
//遍历输出数组数据
public static void printfArray(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + "\t");
}
}
}
输出结果
](https://img-blog.csdnimg.cn/direct/b66ab2c76dd94eaba95362b880f3209d.png)