DoubleRight The past of the world Blog's

插入排序 Java 示例

插入排序 Java 示例

原文： https://howtodoinjava.com/algorithm/insertion-sort-java-example/

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

插入排序的想法来自我们的日常生活经验。 例如，当您与朋友一起玩纸牌时，会将您挑选的下一张纸牌插入手中的已排序纸牌中。

插入排序算法

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

  1. 数据元素分为两部分：已排序部分和未排序部分。
  2. 从未排序的部分中获取一个元素。
  3. 根据可比属性，将元素插入排序部分的正确位置。
  4. 重复步骤 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;
			}
		}
	}
}

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

当然，它具有更多的代码行，但是肯定会提高整体排序时间的性能。

学习愉快！

参考： https://en.wikipedia.org/wiki/Insertion_sort

搜索