排序算法：选择排序、插入排序、快速排序、归并排序的原理与实现

排序，是编程里最基础也最常碰到的操作之一。我做了这么多年嵌入式开发，几乎每个项目都离不开排序——从传感器数据整理到任务调度优先级排列。今天咱们就把四种经典排序算法掰开揉碎讲清楚。

说实话，刚入行那会儿我也觉得排序嘛，能排出来就行。后来在实时系统里踩过坑才明白：选错排序算法，轻则响应变慢，重则系统崩溃。所以这一章，咱们不光要懂原理，更要学会在什么场景下选什么算法。

一、选择排序——最直观的排序

选择排序的思路特别简单：每次从待排序的数据中找出最小的那个，放到最前面。就像你手里有一把扑克牌，一张张挑最小的往桌上摆。

原理

遍历数组，找到最小值的位置，然后跟第一个元素交换。接着从第二个位置开始，重复这个过程。

代码实现

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

复杂度分析

指标	值
最好情况	O(n²)
最坏情况	O(n²)
平均情况	O(n²)
空间复杂度	O(1)
稳定性	不稳定

二、插入排序——像整理扑克牌

插入排序的思路更贴近生活：你打牌的时候，摸到一张新牌，会把它插到手里已经排好序的牌中合适的位置。插入排序就是干这个的。

原理

从第二个元素开始，把它跟前面的元素比较，找到合适的位置插入。前面的元素依次后移。

代码实现

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

复杂度分析

指标	值
最好情况	O(n)
最坏情况	O(n²)
平均情况	O(n²)
空间复杂度	O(1)
稳定性	稳定

三、快速排序——分而治之的典范

快速排序是实际应用中最常用的排序算法。C标准库里的qsort就是它。为什么叫「快速」？因为它平均性能确实好。

原理

选一个基准值（pivot），把小于基准的放左边，大于基准的放右边。然后对左右两部分递归执行同样的操作。

代码实现

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    int j, temp;
    
    for (j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;
}

void quick_sort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quick_sort(arr, low, pi - 1);
        quick_sort(arr, pi + 1, high);
    }
}

复杂度分析

指标	值
最好情况	O(n log n)
最坏情况	O(n²)
平均情况	O(n log n)
空间复杂度	O(log n)
稳定性	不稳定

四、归并排序——稳定且高效

归并排序是另一种分治思想的应用。它先把数组拆成单个元素，再两两合并成有序序列。说白了就是「先拆后合」。

原理

把数组从中间分成两半，分别排序，然后合并两个有序数组。递归进行，直到每个子数组只有一个元素。

代码实现

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int L[n1], R[n2];
    int i, j, k;
    
    for (i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];
    
    i = 0; j = 0; k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    while (i < n1) {
        arr[k] = L[i];
        i++; k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++; k++;
    }
}

void merge_sort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        merge_sort(arr, left, mid);
        merge_sort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

复杂度分析

指标	值
最好情况	O(n log n)
最坏情况	O(n log n)
平均情况	O(n log n)
空间复杂度	O(n)
稳定性	稳定

五、四种排序算法对比

算法	平均时间	最坏时间	空间	稳定	适用场景
选择排序	O(n²)	O(n²)	O(1)	否	小数据量，交换次数少
插入排序	O(n²)	O(n²)	O(1)	是	基本有序的数据
快速排序	O(n log n)	O(n²)	O(log n)	否	通用场景，大数据量
归并排序	O(n log n)	O(n log n)	O(n)	是	需要稳定排序，内存充足

六、知识体系总览

下面这张图帮你理清这四种排序算法的核心逻辑和关系：

七、实际项目中的选择建议

说了这么多理论，咱们聊聊实际怎么选。我个人总结了几条经验：

• 数据量小于50：直接用插入排序。代码简单，而且在小数据量下性能不差。
• 数据基本有序：插入排序是王者。我在处理日志文件时经常用。
• 数据量大且内存充足：快速排序是首选。C标准库都选它，你想想看为什么？
• 需要稳定排序：归并排序。比如按时间戳排序后还要保持原始顺序。
• 内存极度受限：快速排序（原地排序）或插入排序。