Java寫出插入排序演算法的方法和原理

插入排序演算法的步驟與想法

插入排序是一種簡單直觀的排序演算法，它的基本思想是將待排序的元素插入到已排序序列的合適位置上。

具體步驟如下：

1. 首先，我們將陣列分成兩部分：已排序部分和未排序部分。初始時，已排序部分只有一個元素，就是陣列的首元素。
2. 我們從未在排序部分依序取出一個元素，將它與已排序部分的元素逐一比較，找到合適的位置插入。
3. 在比較的過程中，我們將已排序部分的元素向後移動，為插入元素騰出位置。
4. 最後，我們將未排序部分的元素全部插入到已排序部分的合適位置上，排序完成。

下面是用Java語言寫插入排序演算法的範例程式碼：

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 1, 9, 3};
        System.out.println("原数组：");
        printArray(arr);
        insertionSort(arr);
        System.out.println("排序后的数组：");
        printArray(arr);
    }

    public static void printArray(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

在這個程式碼範例中，我們定義了一個insertionSort方法，它接受一個整數數組作為參數，並對數組進行插入排序。我們用n表示陣列的長度，並使用for循環遍歷未排序部分的元素。在每一次遍歷中，我們將目前元素arr[i]儲存到key變數中，然後向前遍歷已排序部分，找到適當的位置插入key。在比較的過程中，我們將較大的元素往後移動一位，為key#騰出位置。最後，我們將key插入到正確的位置上，排序完成。

在main方法中，我們初始化一個整數陣列arr，並呼叫insertionSort方法對陣列進行排序。最後，我們呼叫printArray方法列印排序後的陣列。

透過執行上述程式碼，可以得到如下的輸出結果：

原数组：
5 2 8 1 9 3 
排序后的数组：
1 2 3 5 8 9 

插入排序演算法的時間複雜度為O(n^2)，其中n是陣列的長度。儘管插入排序演算法的時間複雜度較高，但它的實作簡單，適用於小規模的陣列排序。同時，在實際應用中，插入排序演算法也具有穩定性的特性。

以上是Java寫出插入排序演算法的方法和原理的詳細內容。更多資訊請關注PHP中文網其他相關文章！