# 插入排序 Java 示例 > 原文： [https://howtodoinjava.com/algorithm/insertion-sort-java-example/](https://howtodoinjava.com/algorithm/insertion-sort-java-example/) **插入排序**是一种简单而缓慢的排序算法，它反复从未排序部分中提取下一个元素，然后将其插入正确位置的已排序部分中。 插入排序的想法来自我们的日常生活经验。 例如，当您与朋友一起玩纸牌时，会将您挑选的下一张纸牌插入手中的已排序纸牌中。 ## 插入排序算法 **插入排序算法**的基本思想可以描述为以下步骤： 1. 数据元素分为两部分：已排序部分和未排序部分。 2. 从未排序的部分中获取一个元素。 3. 根据可比属性，将元素插入排序部分的正确位置。 4. 重复步骤 2 和 3，直到未排序的部分中没有剩余的元素。 ## 插入排序优势 尽管插入排序显然比[**归并排序**](//howtodoinjava.com/algorithm/merge-sort-java-example/)等其他排序算法要慢，但是在某些情况下它具有一些良好的优点： * 对小型数据输入集有效 * 它是**自适应**，即对于已基本排序的数据集有效 * **稳定**； 即不使用相同的键更改元素的相对顺序 * 在线； 即可以对列表进行排序 ## 插入排序 Java 实现 ```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] ``` ## 插入排序性能改进 如果查看以前的实现，则可以轻松地确定遍历数组以在已排序的数组中找到正确的位置，这似乎是大多数时间的任务，可以使用更快速的搜索算法轻松地对其进行改进。 正如我们看到的那样，数组已经排序，因此我们可以采用**二分搜索算法**，该算法对于已排序的数组更有效。 因此，我们的改进的插入排序算法将变为： ```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 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](https://en.wikipedia.org/wiki/Insertion_sort)