App下載

通俗易懂:插入排序算法全解析

倚靠窗畔 2023-12-05 15:01:36 瀏覽數(shù) (1595)
反饋

插入排序算法是一種簡單直觀的排序算法,它的原理就像我們玩撲克牌時整理手中的牌一樣。下面我將用通俗易懂的方式來解釋插入排序算法的工作原理。 

假設我們手上有一副無序的撲克牌,我們的目標是將它們從小到大排列起來。插入排序算法的思想是,我們從第二張牌開始,逐個將后面的牌插入到已排序的部分中。這樣,我們每次插入一張牌,已排序的部分就多了一張牌,直到所有的牌都被插入到正確的位置。 

飛書20231205-150051

現(xiàn)在,讓我們通過一個簡單的例子來演示插入排序算法的過程。假設我們有以下一組數(shù)字需要排序:[5, 2, 4, 6, 1, 3]。 

  1. 我們從第二個數(shù)字開始,也就是數(shù)字2。我們將2與前面已排序的部分進行比較,如果它小于前面的數(shù)字,就將它插入到該數(shù)字的前面。在這個例子中,2比5小,所以我們將2插入到5的前面,得到[2, 5, 4, 6, 1, 3]。 
  2. 接下來,我們將數(shù)字4與前面的數(shù)字進行比較。4比5小,所以我們將4插入到5的前面,得到[2, 4, 5, 6, 1, 3]。 
  3. 然后,我們將數(shù)字6與前面的數(shù)字進行比較。6比5大,所以它應該放在5的后面。此時,已排序部分為[2, 4, 5],所以我們得到[2, 4, 5, 6, 1, 3]。 
  4. 我們繼續(xù)這個過程,將數(shù)字1插入到已排序部分中。1比2小,所以我們將1插入到2的前面,得到[1, 2, 4, 5, 6, 3]。然后,我們將數(shù)字3插入到已排序部分中。3比2大,但比4小,所以我們將3插入到4的前面,得到[1, 2, 3, 4, 5, 6]。 
  5. 最后,所有的數(shù)字都被插入到正確的位置,得到一個有序的數(shù)組:[1, 2, 3, 4, 5, 6]。 通過這個例子,我們可以看到插入排序算法的基本思想。它通過逐個將未排序的元素插入到已排序的部分中,逐步構建有序的序列。這個過程類似于整理撲克牌,每次插入一張牌,整個序列就會變得更加有序。

演示動畫如下:

飛書20231205-145043

插入排序算法(C/C++)示例代碼如下:

#include <stdio.h>

void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

int main() {
    int arr[] = {5, 2, 4, 6, 1, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("原始數(shù)組: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    insertionSort(arr, n);

    printf("排序后的數(shù)組: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

//代碼輸出
//原始數(shù)組: 5 2 4 6 1 3
//排序后的數(shù)組: 1 2 3 4 5 6zo

總結

通過這個例子,我們可以看到插入排序算法的基本思想。它通過逐個將未排序的元素插入到已排序的部分中,逐步構建有序的序列。這個過程類似于整理撲克牌,每次插入一張牌,整個序列就會變得更加有序。雖然插入排序算法在處理小規(guī)模數(shù)據(jù)時表現(xiàn)良好,但對于大規(guī)模數(shù)據(jù)來說,它的效率相對較低。在實際應用中,我們可能會選擇更高效的排序算法,如快速排序或歸并排序。但是,了解插入排序算法的原理對于理解排序算法的工作方式和思想是非常有幫助的。

1698630578111788

如果你對編程知識和相關職業(yè)感興趣,歡迎訪問編程獅官網(wǎng)(http://m.hgci.cn/)。在編程獅,我們提供廣泛的技術教程、文章和資源,幫助你在技術領域不斷成長。無論你是剛剛起步還是已經(jīng)擁有多年經(jīng)驗,我們都有適合你的內容,助你取得成功。

0 人點贊