如果你是程式設計師，你一定已經聽過很多排序。排序基本上是按升序或降序排列元素。有許多排序演算法可用於對元素進行排序，並且每種演算法都有不同的排序方式、不同的複雜度。所以使用哪種演算法取決於特定的場景和元素的數量。插入也是常用的排序演算法之一，複雜度為 O(n^2)，就像我們對手中的撲克牌進行排序一樣。在本主題中，我們將學習 Java 中的插入排序。
開始您的免費軟體開發課程
網頁開發、程式語言、軟體測試及其他
Java 中插入排序是如何運作的？
讓我們透過一個例子來了解插入排序的工作原理。
假設有一個名為 arr 的數組，其中包含以下元素：
10 5 8 20 30 2 9 7
步驟#1 – 插入排序從陣列的第二個元素（即 5）開始，考慮陣列的第一個元素本身。現在將元素 5 與 10 進行比較，因為 5 小於 10，所以將 10 向前移動 1 個位置，並在其前面插入 5。
現在結果陣列是：
5 10 8 20 30 2 9 7
步驟 #2 – 現在將元素 arr[2]（即 8）與元素 arr[1]（即 10）進行比較。由於 8 比其前面的元素 10 小，因此將其移位一位從它的位置向前一步，然後與5比較。由於8大於5，所以將其插入到它的後面。
那麼結果數組是：
5 8 10 20 30 2 9 7
第 3 步 – 現在將元素 20 與 10 進行比較，因為它大於 10，因此它保持在原來的位置。
5 8 10 20 30 2 9 7
步驟 #4 – 將元素 30 與 20 進行比較，由於它大於 20，因此不會進行任何更改，數組保持原樣。現在數組將是
5 8 10 20 30 2 9 7
步驟#5 – 元素2 與30 進行比較，因為它小於30，所以向前移動一位，然後與20,10,8,5 逐一進行比較，所有元素都移動到前面1 個位置，2 個元素插入到5 個元素之前。
結果數組是：
2 5 8 10 20 30 9 7
步驟 #6 – 將元素 9 與 30 進行比較，因為它小於 30；與20、10一一比較，元素向前移動1位，9插入到10之前、8之後。
結果數組是：
2 5 8 9 10 20 30 7
步驟#7 – 元素7 與30 比較，由於它小於30，因此與30, 20, 10, 9, 8 比較，所有元素都移動1 個位置一一向前，7插在8之前。
產生的陣列將變成：
2 5 7 8 9 10 20 30
這樣，陣列的所有元素都使用插入排序進行排序，開始與前面的元素進行比較。
在 Java 中實作插入排序的範例
Java中的插入排序是一種簡單的排序演算法，適用於所有小資料集。
代碼：
public class InsertionSort {
public static void insertionSort(int arr[]) { for (int j = 1; j < arr.length; j++) { int key = arr[j]; int i = j-1;
while ( (i > -1) && ( arr[i] > key ) ) { arr[i+1] = arr[i]; i--; }
arr[i+1] = key;
}
}
static void printArray(int arr[]) { int len = arr.length;
//simple for loop to print the elements of sorted array for (int i= 0; i<len; i++)
System.out.print(arr[i] + " " );
System.out.println();
}
public static void main(String args[]){ int[] arr1 = {21,18,15,23,52,12,61};
//calling the sort function which performs insertion sort insertionSort(arr1);
//calling the printArray function which performs printing of array printArray(arr1);
}
}登入後複製
輸出：
12 15 18 21 23 52 61
說明：
- 在上面的插入排序程序中，insertionSort()函數用於對原始數組元素進行排序。排序從第二個元素開始，因為第一個元素認為本身已排序。所以‘j’的循環是從陣列的索引1開始的。 「i」是追蹤「j」之前索引的變量，以便比較值。 ”
- key' 是儲存要排列在排序位置的目前元素的值的變數。如果目前值小於最左邊的值，則執行while()循環，進行元素的移位，最後將目前元素插入右側位置。 printArray() 函數用於最終列印排序後的陣列。
1.最佳案例
在插入排序中，最好的情況是數組的所有元素都已排序。因此，當任何元素與其最左邊的元素進行比較時，它總是更大，因此不會處理元素的移位和插入。在這種情況下，最好的情況複雜度是線性的，即 O(n)。
2.最壞的情況
在上面的插入排序代碼中，最壞的情況是數組處於逆序狀態，因此每次將元素與最左邊的元素進行比較時，它總是較小，然後與所有前面的元素進行比較放置、移動和插入完成。在這種情況下，插入排序的複雜度是 O(n^2)。
3.平均情況
即使在平均情況下，插入排序也具有 O(n^2) 複雜度，其中某些元素不需要移位，而某些元素會從其位置移位並在正確位置執行插入。
4.最佳使用
插入排序最適合當數組的大小不是很大，或者只需要對少量元素進行排序，幾乎所有元素都已排序，只需要進行一些更改時。插入排序是小尺寸數組最快的演算法之一，甚至比快速排序還要快。事實上，快速排序在對數組的小部分進行排序時使用插入排序。
結論
上面的解釋清楚地展示了Java中插入排序的工作原理和實作。在其他程式語言中，執行插入排序的邏輯也保持不變，只是語法改變了。在實作任何排序演算法之前，對需要排序的場景進行一些分析非常重要，因為並不是每種排序演算法都適合所有場景。
以上是Java中的插入排序的詳細內容。更多資訊請關注PHP中文網其他相關文章！
