直接插入排序演算法詳解與 C 語言實現

編輯：關於C語言

直接插入排序核心概念

直接插入排序是一種直觀且基礎的排序演算法。其核心思路是將待排序序列劃分為「有序區」與「無序區」兩部分。初始時，有序區僅包含第一個元素，其餘元素屬於無序區。演算法每次從無序區取出首個元素，將其插入有序區的適當位置，使有序區始終保持有序狀態，直到無序區為空。

演算法流程詳細解析

演算法由雙層嵌套迴圈構成：

外層迴圈：從第二個元素（索引 1）開始遍歷，每次確定一個待插入元素。
內層迴圈：將待插入元素與有序區元素從右向左比較。若有序區元素大於待插入值，則將該元素向右移動一位；否則停止比較，將待插入值放入空出的位置。

此過程類似整理撲克牌：每拿一張新牌，從手中已排好序的牌的最右側開始比較，找到合適位置插入。

C 語言完整實現代碼

#include <stdio.h>
#include <stdlib.h>

void InsertSort(int arr[], int n) {
    int i;
    for (i = 1; i < n; i++) {          // 從第 2 個元素開始
        int temp = arr[i];             // 暫存待插入值
        int j = i - 1;
        while (j >= 0 && arr[j] > temp) { // 從右向左尋找插入點
            arr[j + 1] = arr[j];       // 元素右移
            j--;
        }
        arr[j + 1] = temp;             // 插入到正確位置
    }
}

void print(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {9, 1, 5, 8, 3, 7, 4, 6, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("排序前：\n");
    print(arr, n);
    InsertSort(arr, n);
    printf("排序後：\n");
    print(arr, n);
    return 0;
}