詳解Java實作的插入排序演算法

Java插入排序演算法的實作方法詳解

插入排序是一種簡單直覺的排序演算法，它的原理是將待排序的數列分成已排序和未排序兩部分，每次從未排序中取出一個元素，插入到已排序的合適位置。插入排序演算法的實作方法相對簡單，以下將詳細介紹其具體實作方法，並給出對應的程式碼範例。

1. 演算法想法
   假設要對一個整數數組arr進行升序排序，初始時將arr[0]視為已排序的部分，其餘元素視為未排序的部分。以此為基礎，若目前待插入的元素為arr[i]（i從1開始），則從已排序的部分arr[0:i-1]中找到arr[i]應該插入的位置j，將arr[i]插入到位置j，同時將arr[j:i-1]的所有元素依序向後移動一個位置。
2. 程式碼實作
   以下給出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;

            // 将已排序的元素依次向后移动，直到找到arr[i]应该插入的位置
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }

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

3. 演算法分析
   插入排序演算法的時間複雜度為O(n^2)，其中n為待排序的元素個數。在最好的情況下，即待排序數組已經有序，插入排序的時間複雜度為O(n)。在最壞的情況下，待排序數組逆序，插入排序的時間複雜度為O(n^2)。插入排序是一種穩定的排序演算法，因為相等元素的相對位置在排序前後不會改變。

綜上所述，本文詳細介紹了Java插入排序演算法的實作方法，並給出了對應的程式碼範例。插入排序是一種簡單直覺的排序演算法，適用於小規模的陣列或基本上有序的陣列。在實際應用中，可以透過其他更有效率的排序演算法來替代插入排序，但理解插入排序的原理和實作方法對於學習其他排序演算法是非常有益的。

以上是詳解Java實作的插入排序演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！