插入排序 Java 示例 · HowToDoInJava 中文系列教程

# 插入排序 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)