Java 中的插入排序

數組排序是 Java 初學者應該知道的最常見的操作之一。儘管數組並不總是排列數據的最方便方式，而且這主要適用於小數，但數組排序背後的概念在復雜的軟件和數據科學中有大量應用。在這篇文章中，我們將仔細研究什麼是插入排序。我們提供了一些示例和練習題來幫助您完全掌握這個概念。

什麼是插入排序？

基本上，插入排序是開發人員用來組織小數字字符串的算法。它將所有值分成兩個堆棧 - 一個已排序的堆棧和一個未排序的堆棧。一個一個地，“未排序”堆棧中的數字被挑選出來並按正確的順序排列。 Java 中的插入排序 - 1

讓我們仔細看看插入排序的輸入和輸出：

輸入：具有未排序數字元素的數組 A：A[0,1, n, n-2...]。
輸出：包含相同數字但完全排序的數組。這個通常稱為 B：B[0]B[1]...B[n-1]。

有幾種使用插入排序的方法 - 以下是最流行的：

數值排序（升序）：[1, 2, 3, 4, 5]
數值排序（降序）：[5, 4, 3, 2, 1]
按字母排序：[a, b, c, d]

注意：如果你有一個空數組或一個單例，這些被認為是默認排序的。

理解插入排序理論

在探索插入排序背後的代碼之前，讓我們使用非技術語言分解算法。因為我們將展示升序排序的代碼，所以在這篇文章中逐步解釋算法是有意義的。步驟 1.迭代 betweenarr[1]和arr[n]wheren是一個通常小於 10 的數值。步驟 2.使用該方法將您選擇的元素（稱為）key與序列中的前一個數字進行比較sort()。步驟 3.如果所有元素都小於它們的後繼元素，重複比較直到找到更大的值。第 4 步。交換一個較大的值超出較小的位置以創建有序序列。步驟 5.重複這個過程，直到你得到一個排序好的字符串

排序原始數組

由於該算法是最直接的 Java 操作之一，因此即使是完全的初學者在實現它時也不會有太多困難。這是對數組進行排序的分步指南

1.聲明一個用於排序的數組

首先，讓我們創建一個值字符串，稍後我們將使用 Java 顯示這些值。要使用插入排序，您需要創建一個數組。為此，使用int[]


int[] arrayA = {10, 14, 20, 30};

2.使用sort_arr實現算法

sort_arr 方法是實現插入排序最常用的方法之一。在實踐中，它看起來像這樣：


for(int i=0; i< sort_arr.length; ++i){
        int j = i;

3.創建循環和迭代器

通過在插入排序算法中使用循環，開發人員不必為每個元素重複邏輯。雖然創建循環看起來很複雜，但其實很簡單 - 下面是一個示例：


for(int i=0; i< sort_arr.length; ++i){

現在您有了一個正常運行的循環，是時候創建一個迭代器，它將按照所需的順序對所有元素進行排序。從現在開始，我們將迭代器稱為“ j”。

        int j = i;

4. 創建一個“while 循環”

當談到插入排序時，“while”循環對於新的排序數組是必不可少的。要將其設置為升序插入排序，開發人員需要滿足兩個條件：

分配給 j 的值必須大於 0
分配給的值j-1需要大於j索引

一旦 while 循環中的兩個條件都為真，數組的鍵值將等於索引j。

5.數組排序

設置 while 循環後，將交換j和值，直到 while 循環中的一個或兩個條件失敗。j-1類似地，將對 for 循環中的每個值重複排序，直到 for 循環條件也失敗為止。以下是插入排序過程在實踐中的工作原理：


int key = sort_arr[j];
          sort_arr[j] = sort_arr[j-1];
          sort_arr[j-1] = key;
          j = j-1;

排序 ArrayList

儘管理解插入排序背後的數學原理很重要，但在實際軟件開發中，您對 ArrayList 的排序要多於原始數組中的序列。下面是對 ArrayList 進行排序的分步指南：

Element為屬於集合的項目創建一個新類。


public class Element {
    private int id;

    public Element(int id) {
        this.id = id;
    }

在一個集合中，有一個compareTo()方法——我們將使用它來比較兩個元素的 ID。


    public int compareTo(Element element) {
        int res = 0;
        if (this.id < element.getId()) {
            res = -1;
        }
        if (this.id > element.getId()) {
            res = 1;
        }
        return res;
    }
}

應用該算法並創建一些循環來對對象進行排序ArrayList而不是比較它們。


public static void insertionSortArrayList(List<element> list) {
    for (int j = 1; j < list.size(); j++) {
        Element current = list.get(j);
        int i = j-1;
        while ((i > -1) && ((list.get(i).compareTo(current)) == 1)) {
            list.set(i+1, list.get(i));
            i--;
        }
        list.set(i+1, current);
    }
}

您還可以向中添加更多元素ArrayList，如下所示：


List<element> list = new ArrayList<>();

// Create elements w/ IDs 0-24
for (int i = 0; i < 25; i++) {
    list.add(new Element(i));
}

// To use insertion sort, shuffle the values
Collections.shuffle(list);

現在是排序的時候了：


// This helps print values before sorting
list.forEach(e -> System.out.print(e.getId() + ", "));

// Sort the list
insertionSortArrayList(list);

System.out.println();

// Display a sorted array 
list.forEach(e -> System.out.print(e.getId() + ", "));

現在讓我們比較輸入和輸出以確保我們沒有出錯。這是我們用作示例的字符串的比較。
```
4, 2, 6, 7, 0, 5, 9, 1, 8, 3,
0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
```

插入排序練習題

現在您已經掌握了這種排序算法，是時候考驗您的理論和實踐技能了。理論測驗 #1 給定一個數組 [1, 4, 6, 8] 並向其中添加一個新元素 n = 7。你需要進行多少次比較才能得到一個排序的數字序列？指示數組中索引 n 的最終值。理論測驗 #2 在求職面試中，團隊負責人要求您證明排序插入是一種低效的方法。給定一個數字字符串 [0, 3, 6, 8, 9]，您的輸入序列的順序應該是什麼才能最大化排序所需的運行時間？練習題使用 Java 的插入排序對 [0, 1, 4, 5, 2, 3, 7, 9, 8] 數組進行升序排序。

結論

掌握插入排序的最大挑戰是理解這個過程是如何工作的。一旦掌握了它，將模板轉換為代碼就是小菜一碟。只要你不斷地練習和復習相關的練習題，你就會迅速提高你的插入排序速度。