今天，我们将研究插入排序Java程序。
插入排序与Bubble排序类似，在本文中，我们将通过插入排序算法(示例)，然后编写插入排序Java代码对整数数组进行排序。

Java中的插入排序

• 在Java插入排序中，我们将比较所有先前元素中任何索引处的值，直到找到所有较小的值。

• 然后，将值放在没有较小值的索引处。

• 以上两个步骤以迭代方式完成到最后一个索引，最后我们得到了一个排序的整数数组。

插入排序算法示例

让我们通过一个示例来了解插入排序算法。
假设我们有一个未排序的数组[5，4，14，2，2，8]。

• 第一个索引迭代：第一个索引的值= 4，小于5，所以数组变为[5，5，14，2，2，8]，当我们到达起点时，将值放在第0个索引处，数组变为[4， 5，14，2，8]
• 第二索引迭代：第二索引= 14处的值大于5，因此将数组保留原样。
  现在数组= [4、5、14、2、8]
• 第三索引迭代：第三索引= 2处的值小于14，因此数组变为[4、5、14、14、8]，再次2小于5，因此数组变为[4、5、5、14， 8]。
  同样2小于4，因此数组变为[4、4、5、14、8]。
  当我们到达数组的开头时，我们将2放在第0个索引处，并且数组变为[2，4，5，14，8]
• 第4个索引迭代：第4个索引处的值= 8，因此数组变为[2，4，5，5，14，14]，然后8大于5，因此将8放在第14位，数组变为[2，4，5， 8、14]。
  现在，我们的数组已排序。

Java插入排序

在Java程序中编写插入排序实现时要记住的要点：

• 从第二个元素开始到数组的最后一个元素，因此使用for循环。

• 将值存储到另一个变量中，以避免在我们之间更改索引值时丢失它。

• 我们需要不断更改值，直到我们在第0个索引处，或者发现先前值更大为止，因此我们可以为此使用while循环。

这是基于上述示例和关键点的Java中插入排序的实现。

package com.theitroad.test;

import java.util.Arrays;

public class InsertionSort {

	public static void main(String[] args) {
		int A[] = new int[10];
		populateArray(A);
		System.out.println("Before Sorting: ");
		printArray(A);
		//sort the array
		insertionSort(A);
		System.out.println("\nAfter Sorting: ");
		printArray(A);
	}

	/**
	 * This method will sort the integer array using insertion sort in java algorithm
	 * 
	 * @param arr
	 */
	private static void insertionSort(int[] arr) {
		for (int i = 1; i < arr.length; i++) {
			int valueToSort = arr[i];
			int j = i;
			while (j > 0 && arr[j - 1] > valueToSort) {
				arr[j] = arr[j - 1];
				j--;
			}
			arr[j] = valueToSort;
		}
	}

	public static void printArray(int[] B) {
		System.out.println(Arrays.toString(B));
	}

	public static void populateArray(int[] B) {
		for (int i = 0; i < B.length; i++) {
			B[i] = (int) (Math.random() * 100);
		}
	}
}

我正在使用随机数生成器代码，上述程序的输出为：

Before Sorting: 
[57, 90, 80, 48, 35, 91, 1, 83, 32, 53]

After Sorting: 
[1, 32, 35, 48, 53, 57, 80, 83, 90, 91]

插入排序复杂度

对于最佳情况(已排序的数组)，插入排序的复杂度为O(n)，对于最坏情况(以相反顺序排序)，插入复杂度为O(n2)。

Java中的插入排序是小尺寸数组的很好选择，并且当您知道大多数值将被排序时。
例如，对大小为100的数组进行排序时，您知道所有值都将在1到10之间。
这全部用于java中的插入排序。