插入排序算法

插入排序算法的基本思想可以描述为以下步骤：

• 数据元素分为两个部分：已排序部分和未排序部分。
• 从未排序部分中取出一个元素。
• 根据可比较的属性，将元素插入到已排序部分的正确位置。
• 重复步骤 2和步骤 3，直到未排序部分中没有更多元素。

插入排序是一种简单而缓慢的排序算法，它反复从未排序部分中取出下一个元素，并将其插入到已排序部分的正确位置。

插入排序 Java 实现

public class InsertionSortExample 
{
	public static void main(String[] args) 
	{
		//This is unsorted array
		Integer[] array = new Integer[] {12,13,24,10,3,6,90,70};

		//Let's sort using insertion sort
		insertionSort(array, 0, array.length);

		//Verify sorted array
		System.out.println(Arrays.toString(array));
	}
	@SuppressWarnings({ "rawtypes", "unchecked" })
	public static void insertionSort(Object[] a, int fromIndex, int toIndex) 
	{
		Object d;
		for (int i = fromIndex + 1; i < toIndex; i++) 
		{
			d = a[i];
			int j = i;
			while (j > fromIndex && ((Comparable) a[j - 1]).compareTo(d) > 0) 
			{
				a[j] = a[j - 1];
				j--;
			}
			a[j] = d;
		}
	}
}
Output: [3, 6, 10, 12, 13, 24, 70, 90]

插入排序性能改进

如果我们查看以前的实现，那么我们可以很容易地确定迭代数组以在已排序的数组中找到正确的位置似乎是最耗时的任务，并且可以使用更快速的搜索算法轻松改进。

正如我们看到的数组已经排序，所以我们可以使用对已经排序的数组更有效的二分搜索算法。
所以我们的“改进的插入排序算法”将变成：

public class InsertionSortExample 
{
	public static void main(String[] args) 
	{
		// This is unsorted array
		Integer[] array = new Integer[] { 12, 13, 24, 10, 3, 6, 90, 70 };
		// Let's sort using insertion sort
		insertionSortImproved(array, 0, array.length);
		// Verify sorted array
		System.out.println(Arrays.toString(array));
	}
	@SuppressWarnings({ "rawtypes", "unchecked" })
	public static void insertionSortImproved(Object[] a, int fromIndex, int toIndex) 
	{
		Object d;
		for (int i = fromIndex + 1; i < toIndex; i++)
		{
			d = a[i];
			int jLeft = fromIndex;
			int jRight = i - 1;
			//Check if its current position is it's suitable position
			if (((Comparable) a[jRight]).compareTo(d) > 0) 
			{
				//Perform binary search
				while (jRight - jLeft >= 2) 
				{
					int jMiddle = (jRight - jLeft) / 2 + jLeft - 1;
					if (((Comparable) a[jMiddle]).compareTo(d) > 0) {
						jRight = jMiddle;
					} else {
						jLeft = jMiddle + 1;
					}
				}
				if (jRight - jLeft == 1) 
				{
					int jMiddle = jLeft;
					if (((Comparable) a[jMiddle]).compareTo(d) > 0) {
						jRight = jMiddle;
					} else {
						jLeft = jMiddle + 1;
					}
				}
				//Place the element
				int j = i;
				for (j = i; j > jLeft; j--) 
				{
					a[j] = a[j - 1];
				}
				a[j] = d;
			}
		}
	}
}

输出：

[3, 6, 10, 12, 13, 24, 70, 90]

插入排序优势

虽然插入排序明显比其他排序算法慢，比如 Merge Sort ，但它在特定情况下有一些很好的优势：

• 对小数据输入集有效
• 它是自适应的，例如：对于已经基本排序的数据集是有效的
• 它是稳定的；例如：不改变具有相同键的元素的相对顺序
• 它是在线的；例如：可以在收到列表时对列表进行排序