Java中的插入排序：一種簡(jiǎn)單且高效的算法

簡(jiǎn)介

在本博客中，我們將學(xué)習(xí)插入排序的工作原理。插入排序是一種簡(jiǎn)單的排序算法，它通過一次一個(gè)元素構(gòu)建最終的排序數(shù)組。對(duì)于小型數(shù)據(jù)集，它的效率較高，并且常作為更復(fù)雜排序算法的一部分使用。

插入排序的工作原理

• 從數(shù)組的第二個(gè)元素開始。
• 將其與前面的元素進(jìn)行比較。
• 如果較小，則將較大的元素向右移動(dòng)。
• 將該元素插入到正確的位置。
• 對(duì)所有元素重復(fù)上述步驟。

import java.util.Arrays;
public class InsertionSortExample {
    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 = {64, 34, 25, 12, 22, 11, 90};
        insertionSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

時(shí)間復(fù)雜度

• 最佳情況：O(n)，當(dāng)數(shù)組已經(jīng)排序時(shí)。
• 平均和最壞情況：O(n²)。

空間復(fù)雜度

• O(1)，因?yàn)樗谠嘏判颉?/li>

優(yōu)點(diǎn)

• 實(shí)現(xiàn)簡(jiǎn)單
• 對(duì)于小型數(shù)據(jù)集效率高
• 自適應(yīng)（對(duì)于部分排序的數(shù)組高效）。

缺點(diǎn)

• 對(duì)于大型數(shù)據(jù)集效率低。

總結(jié)

插入排序在數(shù)據(jù)幾乎已排序或排序小型數(shù)組的場(chǎng)景中表現(xiàn)良好。它的簡(jiǎn)單性使其成為教育目的和作為更復(fù)雜算法的構(gòu)建塊的良好選擇。

若你想提升Java技能，可關(guān)注我們的Java培訓(xùn)課程。