您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> C 語言入門

C語言經典排序與查找算法實戰：選擇、插入、二分查找完整實現

編輯：C 語言入門

排序算法篇

1. 選擇排序

核心思想：每輪從無序區選最小元素，與無序區首元素交換。

void selection_sort(int arr[], int n) {
    for (int i = 0; i < n - 1; ++i) {
        int min_idx = i;
        for (int j = i + 1; j < n; ++j)
            if (arr[j] < arr[min_idx]) min_idx = j;
        if (min_idx != i) {
            int tmp = arr[i];
            arr[i] = arr[min_idx];
            arr[min_idx] = tmp;
        }
    }
}

時間複雜度：O(n²)，空間 O(1)，不穩定。

2. 插入排序

核心思想：將無序區元素逐個插入有序區適當位置，類似整理撲克牌。

void insertion_sort(int arr[], int n) {
    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;
    }
}

時間複雜度：最好 O(n)（近乎有序），最壞 O(n²)，空間 O(1)，穩定，適合小規模或近乎有序數據。

查找算法篇

1. 順序查找

適用於無序數組，逐個比對，時間 O(n)。

2. 二分查找（折半查找）

前提：數組必須有序。每次取中間元素比較，將搜索範圍減半。

int binary_search(const int arr[], int n, int target) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;  // 防溢出
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;  // 未找到
}

時間複雜度：O(log n)，空間 O(1)。

完整可執行示例

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

void print_arr(const int a[], int n) {
    for (int i = 0; i < n; ++i) printf("%d ", a[i]);
    puts("");
}

int main(void) {
    int data[] = {9, 6, 3, 5, 2, 4, 7};
    int n = sizeof(data) / sizeof(data[0]);

    puts("原始數據:"); print_arr(data, n);

    selection_sort(data, n);
    puts("選擇排序後:"); print_arr(data, n);

    int arr2[] = {9, 6, 3, 5, 2, 4, 7};
    insertion_sort(arr2, n);
    puts("插入排序後:"); print_arr(arr2, n);

    int sorted[] = {2, 3, 4, 5, 6, 7, 9};
    int pos = binary_search(sorted, 7, 5);
    printf("二分查找 5: 索引 %d\n", pos);  // 輸出 3

    return 0;
}

工程選型指南

算法	適用場景	穩定性	備註
選擇排序	教學演示、極小數據量	不穩定	交換次數少（O(n)）
插入排序	小數據量、近乎有序、線上排序	穩定	標準庫小區間排序常用
二分查找	靜態有序數組、頻繁查找	-	需隨機訪問支援