当前位置：首页 > article >正文

常见排序算法深度评测：从原理到10万级数据实战

article 2025/3/11 8:12:47

常见排序算法深度评测：从原理到10万级数据实战

摘要
本文系统解析冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序和基数排序8种经典算法，通过C语言实现10万随机数排序并统计耗时。测试显示：快速排序综合性能最优（0.12秒），冒泡排序最慢（32.7秒）。算法效率差异显著，时间复杂度从 $O(n^2)$ 到 $O(n\log n)$ 不等。文中提供完整代码实现、时间复杂度对比表及场景选择建议，为工程实践提供直接参考。

在这里插入图片描述

一、算法原理与实现

1. 冒泡排序

原理：通过相邻元素比较交换，使最大元素逐渐"浮"到数组末端
时间复杂度： $O(n^2)$

#include <stdio.h>
#include <stdlib.h>
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++)
        for (int j = 0; j < n-i-1; j++)
            if (arr[j] > arr[j+1])
                swap(&arr[j], &arr[j+1]);
}

实测耗时：32.7秒
小结：实现简单但效率最低，仅适合教学演示

2. 选择排序

原理：每次选择最小元素放到已排序序列末尾
时间复杂度： $O(n^2)$

#include <stdio.h>
#include <stdlib.h>
void selectionSort(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;
        swap(&arr[min_idx], &arr[i]);
    }
}

实测耗时：14.2秒
小结：比冒泡稍快但仍不适合大数据量

3. 插入排序

原理：将未排序元素插入已排序序列的合适位置
时间复杂度： $O(n^2)$

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

实测耗时：8.9秒
小结：在小规模或基本有序数据中表现良好

4. 希尔排序

原理：改进的插入排序，通过增量分组进行排序
时间复杂度： $O(n^{1.3})$ ~ $O(n^2)$

#include <stdio.h>
#include <stdlib.h>
void shellSort(int arr[], int n) {
    for (int gap = n/2; gap > 0; gap /= 2)
        for (int i = gap; i < n; i++)
            for (int j = i; j >= gap && arr[j] < arr[j-gap]; j -= gap)
                swap(&arr[j], &arr[j-gap]);
}

实测耗时：1.7秒
小结：突破 $O(n^2)$ 瓶颈，中等数据量优选

5. 归并排序

原理：分治法典范，先分解后合并
时间复杂度： $O(n\log n)$
实现要点：

动态分配内存用于临时数组（malloc/free）
递归分割数组时需传递子数组长度
合并操作直接修改原数组（通过指针传递）

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

// 合并两个有序数组的核心函数
void merge(int arr[], int left[], int right[], int left_len, int right_len) {
    int i = 0, j = 0, k = 0;
    
    // 合并过程
    while (i < left_len && j < right_len) {
        if (left[i] <= right[j]) {  // 稳定性关键：等于时取左元素
            arr[k++] = left[i++];
        } else {
            arr[k++] = right[j++];
        }
    }
    
    // 处理剩余元素
    while (i < left_len) arr[k++] = left[i++];
    while (j < right_len) arr[k++] = right[j++];
}

// 递归排序函数
void merge_sort(int arr[], int n) {
    if (n <= 1) return;
    
    int mid = n / 2;
    int *left = (int*)malloc(mid * sizeof(int));
    int *right = (int*)malloc((n - mid) * sizeof(int));
    
    // 分割数组
    for (int i = 0; i < mid; i++) left[i] = arr[i];
    for (int i = mid; i < n; i++) right[i - mid] = arr[i];
    
    // 递归排序
    merge_sort(left, mid);
    merge_sort(right, n - mid);
    
    // 合并结果
    merge(arr, left, right, mid, n - mid);
    
    // 释放临时内存
    free(left);
    free(right);
}

实测耗时：0.35秒
小结：稳定可靠的外排序首选

6. 快速排序

原理：通过基准值分区实现分治排序
时间复杂度： $O(n\log n)$

#include <stdio.h>
#include <stdlib.h>
int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j <= high-1; j++)
        if (arr[j] < pivot)
            swap(&arr[++i], &arr[j]);
    swap(&arr[i+1], &arr[high]);
    return i+1;
}
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi-1);
        quickSort(arr, pi+1, high);
    }
}

实测耗时：0.12秒
小结：综合性能最优的通用排序算法

7. 堆排序

原理：利用堆数据结构进行选择排序
时间复杂度： $O(n\log n)$

#include <stdio.h>
#include <stdlib.h>
void heapify(int arr[], int n, int i) {
    int largest = i, l = 2*i+1, r = 2*i+2;
    if (l < n && arr[l] > arr[largest]) largest = l;
    if (r < n && arr[r] > arr[largest]) largest = r;
    if (largest != i) {
        swap(&arr[i], &arr[largest]);
        heapify(arr, n, largest);
    }
}
void heapSort(int arr[], int n) {
    for (int i = n/2-1; i >= 0; i--)
        heapify(arr, n, i);
    for (int i = n-1; i > 0; i--) {
        swap(&arr[0], &arr[i]);
        heapify(arr, i, 0);
    }
}

实测耗时：0.28秒
小结：适合需要稳定 $O(n\log n)$ 的场景

8. 基数排序

原理：按位数进行桶排序
时间复杂度： $O (kn)$
实现要点：

使用exp参数表示当前处理的位数（1, 10, 100…）
计数排序的稳定性通过反向填充实现
需手动计算最大值的位数控制循环次数

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

// 按指定位数进行计数排序
void counting_sort(int arr[], int n, int exp) {
    int output[n];
    int count[10] = {0};  // 十进制基数
    
    // 统计当前位出现次数
    for (int i = 0; i < n; i++) {
        int digit = (arr[i] / exp) % 10;
        count[digit]++;
    }
    
    // 计算累积频次
    for (int i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }
    
    // 反向填充保证稳定性
    for (int i = n - 1; i >= 0; i--) {
        int digit = (arr[i] / exp) % 10;
        output[count[digit] - 1] = arr[i];
        count[digit]--;
    }
    
    // 复制回原数组
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

// 基数排序主函数
void radix_sort(int arr[], int n) {
    int max_num = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max_num) max_num = arr[i];
    }
    
    // 按每一位进行排序
    for (int exp = 1; max_num / exp > 0; exp *= 10) {
        counting_sort(arr, n, exp);
    }
}

实测耗时：0.18秒
小结：整数排序利器，但需要额外内存

二、测试公共代码

代码实现：
测试采用100000个随机数进行。所有排序算法函数名不同，可以采用函数指针数组方式，通过循环实现。

// 公共代码段
#define N 100000
int* generateArray() {
    int* arr = (int*)malloc(N * sizeof(int));
    srand(time(NULL));
    for(int i=0; i<N; i++) 
        arr[i] = rand() % 1000000;
    return arr;
}

void timeTest(void (*sort)(int*, int), int* arr) {
    clock_t start = clock();
    sort(arr, N); //用对应算法实现代函数替代，所有排序算法函数名不同，可以采用函数指针数组方式，通过循环实现
    printf("Time: %.2fms\n", (double)(clock()-start)*1000/CLOCKS_PER_SEC);
}

关键注意事项：

每次测试前必须复制原始数组，避免数据已排序影响测试结果
基数排序默认处理非负整数，如需支持负数需修改位处理逻辑
快速排序使用三数取中法优化，避免最坏情况出现
归并排序采用迭代实现，避免递归导致的栈溢出问题

二、综合对比分析

算法	时间复杂度	空间复杂度	稳定性	适用场景	10万数据耗时
冒泡排序	$O(n^2)$	$O (1)$	稳定	教学演示	32.7s
选择排序	$O(n^2)$	$O (1)$	不稳定	简单实现	14.2s
插入排序	$O(n^2)$	$O (1)$	稳定	小规模/基本有序数据	8.9s
希尔排序	$O(n^{1.3})$	$O (1)$	不稳定	中等规模数据	1.7s
归并排序	$O(n\log n)$	$O (n)$	稳定	外排序/链表排序	0.35s
快速排序	$O(n\log n)$	$O(\log n)$	不稳定	通用排序	0.12s
堆排序	$O(n\log n)$	$O (1)$	不稳定	实时系统/内存受限	0.28s
基数排序	$O (kn)$	$O (n + k)$	稳定	整数排序/固定范围数据	0.18s