企业🤖AI智能体构建引擎,智能编排和调试,一键部署,支持私有化部署方案 广告
# 插入排序 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)