App下載

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

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

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

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

飛書(shū)20231205-150051

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

  1. 我們從第二個(gè)數(shù)字開(kāi)始,也就是數(shù)字2。我們將2與前面已排序的部分進(jìn)行比較,如果它小于前面的數(shù)字,就將它插入到該數(shù)字的前面。在這個(gè)例子中,2比5小,所以我們將2插入到5的前面,得到[2, 5, 4, 6, 1, 3]。 
  2. 接下來(lái),我們將數(shù)字4與前面的數(shù)字進(jìn)行比較。4比5小,所以我們將4插入到5的前面,得到[2, 4, 5, 6, 1, 3]。 
  3. 然后,我們將數(shù)字6與前面的數(shù)字進(jìn)行比較。6比5大,所以它應(yīng)該放在5的后面。此時(shí),已排序部分為[2, 4, 5],所以我們得到[2, 4, 5, 6, 1, 3]。 
  4. 我們繼續(xù)這個(gè)過(guò)程,將數(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ù)字都被插入到正確的位置,得到一個(gè)有序的數(shù)組:[1, 2, 3, 4, 5, 6]。 通過(guò)這個(gè)例子,我們可以看到插入排序算法的基本思想。它通過(guò)逐個(gè)將未排序的元素插入到已排序的部分中,逐步構(gòu)建有序的序列。這個(gè)過(guò)程類似于整理?yè)淇伺?,每次插入一張牌,整個(gè)序列就會(huì)變得更加有序。

演示動(dòng)畫(huà)如下:

飛書(shū)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

總結(jié)

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

1698630578111788

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

0 人點(diǎn)贊