Java中怎么實現 插入排序

Java中怎么實現插入排序

插入排序（Insertion Sort）是一種簡單直觀的排序算法。它的工作原理是通過構建有序序列，對于未排序數據，在已排序序列中從后向前掃描，找到相應位置并插入。插入排序在實現上通常采用in-place排序（即只需用到O(1)的額外空間的排序），因而在從后向前掃描過程中，需要反復把已排序元素逐步向后挪位，為最新元素提供插入空間。

插入排序的基本思想

插入排序的基本思想是將一個記錄插入到已經排好序的有序表中，從而得到一個新的、記錄數增1的有序表。具體步驟如下：

1. 從第一個元素開始，該元素可以認為已經被排序。
2. 取出下一個元素，在已經排序的元素序列中從后向前掃描。
3. 如果該元素（已排序）大于新元素，將該元素移到下一位置。
4. 重復步驟3，直到找到已排序的元素小于或者等于新元素的位置。
5. 將新元素插入到該位置后。
6. 重復步驟2~5，直到所有元素都排序完畢。

Java實現插入排序

下面是一個使用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[0..i-1]中大于key的元素向后移動
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }

    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();
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6};
        System.out.println("排序前的數組:");
        printArray(arr);

        insertionSort(arr);

        System.out.println("排序后的數組:");
        printArray(arr);
    }
}

代碼解析

1. insertionSort方法：這是插入排序的核心方法。它接受一個整數數組作為參數，并對數組進行排序。

   • int n = arr.length; 獲取數組的長度。
   • for (int i = 1; i < n; ++i) 從第二個元素開始遍歷數組。
   • int key = arr[i]; 將當前元素存儲在key中。
   • int j = i - 1; 初始化j為當前元素的前一個位置。
   • while (j >= 0 && arr[j] > key) 在已排序的部分中從后向前掃描，找到合適的位置插入key。
   • arr[j + 1] = arr[j]; 將大于key的元素向后移動。
   • j = j - 1; 繼續向前掃描。
   • arr[j + 1] = key; 將key插入到正確的位置。

2. printArray方法：用于打印數組的內容。

3. main方法：程序的入口，創建一個數組并調用insertionSort方法進行排序，然后打印排序前后的數組。

運行結果

運行上述代碼，輸出結果如下：

排序前的數組:
12 11 13 5 6 
排序后的數組:
5 6 11 12 13 

插入排序的時間復雜度

• 最壞情況：當輸入數組是逆序時，插入排序需要進行O(n^2)次比較和交換。
• 最好情況：當輸入數組已經是有序時，插入排序只需要進行O(n)次比較。
• 平均情況：插入排序的時間復雜度為O(n^2)。

總結

插入排序是一種簡單且易于實現的排序算法，適用于小規模數據的排序。盡管它的時間復雜度較高，但在某些特定情況下（如數據基本有序時），插入排序的性能可能會優于其他更復雜的排序算法。通過理解插入排序的基本思想和實現方式，可以更好地掌握排序算法的核心概念。