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

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

news 来源：原创 2025/8/23 1:10:01

常见排序算法深度评测：从原理到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

工程建议：

通用场景优先选择快速排序
内存敏感时选用堆排序
稳定排序需求使用归并排序
整数排序可尝试基数排序
小规模数据（n<1000）使用插入排序

实际应用时需结合数据特征进行算法选择，必要时可采用混合排序策略。

三、性能优化建议

混合排序策略：当快速排序子数组长度小于15时切换为插入排序
内存预分配：归并排序的临时数组可提前分配避免重复申请
基数排序优化：使用位运算替代除法操作提升计算效率
并行化改造：归并排序和快速排序适合多线程优化

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

常见排序算法深度评测：从原理到10万级数据实战摘要本文系统解析冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序和基数排序8种经典算法，通过C语言实现10万随机数排序并统计耗时。测试显示：快速排序综合性能最优&…...

编程日记 2025/8/23 1:10:01

搭建BOA服务器

BOA服务器是嵌入式常用的服务器类型，嵌入式程序作为后端时候如果想配合网页进行显示，利用BOA服务器搭建网络界面是不错的选择首先下载boa官方安装包 Boa Webserver 下载后传输到Ubuntu随便文件夹，解压 tar -xvf boa-0.94.13.tar.gz 进入…...

编程日记 2025/8/21 18:49:45

JSON.parse(JSON.stringify())深拷贝不会复制函数

深拷贝是指创建一个新对象，并递归地复制原对象中所有层级的属性和值，从而确保新对象与原对象完全独立深拷贝的实现方法 ： 1. 使用 JSON.parse(JSON.stringify()) 函数会被忽略复制，比如，下面的对象的forma…...

编程日记 2025/8/21 23:01:55

debug_unpack_ios failed: Exception: Failed to codesign 解决方案（亲测有效）

debug_unpack_ios failed: Exception: Failed to codesign 解决方案（亲测有效） 背景原因解决方案tipsresult 背景执行flutter doctor全通过后run项目依然报错原因 1、检查flutter Mac的flutter项目在哪个文件夹内 2、检查flutter Sdk在哪个文件夹内 …...

编程日记 2025/8/16 10:01:47

1.docker环境搭建： 1.1软件仓库的配置rhel9： #cd/etc/yum.repos.d #vim docker.repo [docker] namedocker-ce baseurlhttps://mirrors.aliyun.com/docker-ce/linux/rhel/9/x86_64/stable gpgcheck0 1.2安装docker并且启动服务 yum install -y dock…...

编程日记 2025/8/20 14:22:02

【Linux】基本命令

目录 🔥一、基础命令 1.sudo su（superuser do） 2.pwd（print working directory） 3.ls（list） 4.cd（change directory） 5.mkdir（make directory&#xff…...

编程日记 2025/8/22 3:22:28

win10电脑鼠标速度突然变的很慢？

电脑鼠标突然变很慢，杀毒检测后没问题，鼠标设置也没变，最后发现可能是误触鼠标的“DPI”调节键。 DPI调节键在鼠标滚轮下方，再次点击即可恢复正常鼠标速度。如果有和-的按键，速度变快，-速度变慢。图源&…...

编程日记 2025/8/22 18:49:12

前端（vue）学习笔记（CLASS 3）：生命周期工程化开发入门

1、生命周期 Vue生命周期：一个Vue实例从创建到销毁的整个过程生命周期四个阶段：创建、挂载、更新、销毁 1、创建阶段：响应式数据 2、挂载阶段：渲染模板 3、更新阶段：数据修改、更新视图（执行多次&…...

编程日记 2025/8/16 5:30:00

Python写一个查星座的小程序，适合初学者练手——字典和if语句练习

一、界面预览二、完整代码 # 导入必要的库 import tkinter as tk from tkinter import ttk # 导入ttk模块用于更现代的控件 from PIL import Image, ImageTk # 用于处理图片 import os # 用于文件路径操作class ZodiacApp:def __init__(self, root):self.root rootself.r…...

编程日记 2025/8/21 9:53:48

云上特权凭证攻防启示录：从根账号AK泄露到安全体系升级的深度实践

事件全景：一场持续17分钟的云上攻防战 2025年3月9日15:39，阿里云ActionTrail日志突现异常波纹——根账号acs:ram::123456789:root（已脱敏）从立陶宛IP（164.92.91.227）发起高危操作。攻击者利用泄露的AccessKey（AK）在17分钟内完成侦察→提权→持久化攻击链，完整操作序列…...

编程日记 2025/8/21 1:19:11

blazemeter工具使用--用于自动生成jmeter脚本并进行性能测试

1、安装blazemeter（网上有很多详情的教程） 2、开始录制：设置号你的文件名称后开始录制 3、录制完成后保存为jmeter(jmx)文件 4、在jmeter中打开文件 5、添加一个后置处理器：查看结果树，后运行看看能否成功&#xf…...

编程日记 2025/8/18 3:04:02

TypeScript系列07-类型声明文件

在现代前端开发中，TypeScript已成为提升代码质量和开发体验的利器。对于React和React Native项目，合理利用类型声明文件不仅能提供更好的智能提示和类型检查，还能显著减少运行时错误。本文将深入探讨类型声明文件的编写与使用。 1. 声明文件…...

编程日记 2025/8/18 7:02:14

【社交+陪玩服务】全场景陪玩系统源码小程序+H5双端社群互动+即时点单+搭建教程

内容目录一、详细介绍二、效果展示1.部分代码2.效果图展示三、学习资料下载一、详细介绍找搭子系统源码，圈子源码、社交源码、陪玩源码，亲测 100% 可用，跟市场上卖 1w的那款一模一样，功能非常齐全，企业级别运营的…...

编程日记 2025/8/19 20:55:34

【Java并发】【synchronized】适合初学者体质入门的synchronized

👋hi，我不是一名外包公司的员工，也不会偷吃茶水间的零食，我的梦想是能写高端CRUD 🔥 2025本人正在沉淀中… 博客更新速度 👍 欢迎点赞、收藏、关注，跟上我的更新节奏 📚欢迎订阅专栏…...

编程日记 2025/8/19 19:06:26

经销商管理系统选型解析：8款产品详评

本文主要介绍了以下8款经销商管理系统：1.纷享销客； 2.用友T6经销商管理系统； 3.金蝶经销商管理系统； 4.鼎捷经销商管理系统； 5.浪潮经销商管理系统； 6.销售易； 7.SAP Business One Distributor …...

编程日记 2025/8/18 7:02:33

基于STM32的逻辑分析仪

目录制约性能因素协议命令下位机回复CMD_ID的回复CMD_METADATA命令的回复上报的采样数设置使用开源软件PulseView设置操作1．设置采样数2．设置采样频率3.使能或禁止通道4.设置通道的触发条件实现准备汇编指令精确测量时间程序C语言初实现采集数据上报…...

编程日记 2025/8/21 13:55:40

mapbox高阶，结合threejs（threebox）添加管道

👨‍⚕️ 主页： gis分享者 👨‍⚕️ 感谢各位大佬点赞👍 收藏⭐ 留言📝 加关注✅! 👨‍⚕️ 收录于专栏：mapbox 从入门到精通文章目录一、🍀前言1.1 ☘️mapboxgl.Map 地图对象1.2 ☘️mapboxgl.Map style属性1.3 ☘️threebox Tube静态对象二、🍀使用thr…...

编程日记 2025/8/16 9:58:08

使用PySpark进行大数据处理与机器学习实战指南

1. 技术介绍 1.1 PySpark概述 PySpark是Apache Spark的Python API，它结合了Python的易用性和Spark的分布式计算能力，能够高效处理PB级数据集。Spark基于内存计算的特性使其比传统Hadoop MapReduce快10-100倍，支持流处理、SQL查询、机器学习…...

编程日记 2025/8/20 9:38:31

注意力机制-学习

1. 自注意力机制句子："The animal didnt cross the street because it was too tired." 在这个句子中，“it”指的是“animal”. 在自注意力机制中，当我们处理到“it”这个词时，模型会计算“it”与句子中其他所有词的…...

编程日记 2025/8/22 11:55:04

华纳云：香港服务器出现带宽堵塞一般是什么原因?

香港服务器带宽堵塞的原因通常可以归结为以下几个方面： 1. 机房带宽资源有限 (1)香港本地国际带宽成本高香港的国际出口带宽昂贵，机房通常提供的带宽较小(如默认1Mbps-5Mbps)，如果多个用户争抢有限的带宽，就会出现网络拥堵、丢包…...

编程日记 2025/8/21 21:55:57

我们在开发时，什么时候用到虚函数和纯虚函数？

在曾经学习面向对象的概念上，对虚函数和纯虚函数的区别，我们都会止于这样的理解层面：虚函数是用于被子类可继承可重写的函数，而纯虚函数是子类继承后就必须重写的函数。但是在开发工作上，却有很多开发者是没法彻底参透…...

编程日记 2025/8/21 1:32:59

Python：lambda结合if判断，内置函数与拆包

lambda的应用： #a,b是形参，比较大小 complambda a,b:"a<b" if a<b else "a>b" print(comp(8,5)) 特点：lambda只能实现简单的逻辑，如果逻辑复杂且代码量较大，不建议使用lambda降低代码的…...

编程日记 2025/8/22 22:00:15

【Java学习】包装类

面向对象系列九包装类变量一、装箱 1.实例化包装对象 2.静态缓存池 3.写法二、拆箱包装类变量每个基本数据类型都有对应的基本类型的包装类变量，将基本数据类型通过对应的包装类对象载入着进入到类与对象面向对象体系一、装箱 Integer.valueOf(int) —…...

编程日记 2025/8/22 7:02:36

从新手到专家：嵌入式代码空间优化技巧

目录一、基本概念内存开销优化目标二、存储管理数据类型选择变量作用域结构体对齐三、代码结构循环优化函数调用分支语句查表法的动态扩展查表法与算法结合指针替代数组（续）指针与动态内存结合指针与函数指针结合常量优化（续）常量传播与…...

编程日记 2025/8/22 9:51:18

本地部署Navidrome个人云音乐平台随时随地畅听本地音乐文件

文章目录前言1. 安装Docker2. 创建并启动Navidrome容器3. 公网远程访问本地Navidrome3.1 内网穿透工具安装3.2 创建远程连接公网地址3.3 使用固定公网地址远程访问前言今天我要给大家安利一个超酷的私有化音乐神器——Navidrome！它不仅让你随时随地畅享本地音乐…...

编程日记 2025/8/22 8:40:15

AI自动化编程初探

先说vscodeclinemodelscope方案，后面体验trae或者cursor再写写其它的。vscode和trae方案目前来说是免费的，cursor要用claud需要付费，而且不便宜，当然效果可能是最好的。 vscode方案，我的经验是最好在ubuntu上&#xff…...

编程日记 2025/8/16 11:33:22

KUKA机器人：智能制造的先锋力量

在科技日新月异的今天，自动化和智能化已成为推动制造业转型升级的重要引擎。作为全球领先的智能、资源节约型自动化解决方案供应商，KUKA机器人在这一浪潮中扮演着举足轻重的角色。本文将带您深入了解KUKA机器人的发展现状，探索其在智能制造领…...

编程日记 2025/8/22 11:37:15

2021 年 9 月青少年软编等考 C 语言六级真题解析

目录 T1. 合法出栈序列思路分析T2. 奇怪的括号思路分析T3. 区间合并思路分析T4. 双端队列思路分析T1. 合法出栈序列题目链接：SOJ D1110 给定一个由不同小写字母构成的长度不超过 8 8 8 的字符串 x x x，现在要将该字符串的字符依次压入栈中，然后再全部弹出。要求左边的字…...

编程日记 2025/8/20 15:41:26

java快速输入

带解析 package Month3; import java.util.*; import java.io.*; public class Demo100843 {static class Reader{BufferedReader bf new BufferedReader(new InputStreamReader(System.in));StringTokenizer st new StringTokenizer("");String next() throws IO…...

编程日记 2025/8/16 11:16:06

C/C++蓝桥杯算法真题打卡（Day3）

一、P8598 [蓝桥杯 2013 省 AB] 错误票据 - 洛谷算法代码： #include<bits/stdc.h> using namespace std;int main() {int N;cin >> N; // 读取数据行数unordered_map<int, int> idCount; // 用于统计每个ID出现的次数vector<int> ids; …...

编程日记 2025/8/16 12:24:46

AntV_G6实现UI树

UI 树的实现背景目前需要实现一个 UI 树，用于展示设备树，以及设备树中设备的属性。与树状列表不同，UI 树需要有特定的交互方式，支持边以及当前节点的点击事件。实现效果【复制到.html文件夹就看见了】总体效果点击节点效果…...

编程日记 2025/8/22 21:25:54

【0016】Python数据类型-不可变集合详解

如果你觉得我的文章写的不错，请关注我哟，请点赞、评论，收藏此文章，谢谢！ 本文内容体系结构如下： 在Python中，除了我们常见的可变集合（Set）外，还有一种不可…...

编程日记 2025/8/17 18:15:56

学习资料电子版免费下载的网盘网站（非常全！）

我分享一个私人收藏的电子书免费下载的网盘网站（学习资料为主）： link3.cc/sbook123 所有资料都保存在网盘了，直接转存即可，非常的便利！ 包括了少儿，小学，初中，中职&am…...

编程日记 2025/8/20 20:57:41

ROS2学习笔记2

前言本篇文章属于ROS2humble的学习笔记，来源于B站鱼香ROSup主。下面是这位up主的视频链接。本文为个人学习笔记，只能做参考，细节方面建议观看视频，肯定受益匪浅。《ROS 2机器人开发从入门到实践》课程介绍_哔哩哔哩_bilibili …...

编程日记 2025/8/16 11:22:53

为什么大模型网站使用 SSE 而不是 WebSocket？

在大模型网站（如 ChatGPT、Claude、Gemini 等）中，前端通常使用 EventSource（Server-Sent Events, SSE） 来与后端对接，而不是 WebSocket。这是因为 SSE 更适合类似流式文本生成的场景。下面我们详细对比 SSE…...

编程日记 2025/8/20 8:43:28

利用阿里云Atlas地区选择器与Plotly.js实现数据可视化与交互

在数据科学与可视化领域，交互式图表和地图应用越来越成为数据分析和展示的重要手段。本文将介绍如何结合阿里云Atlas地区选择器与Plotly.js，创建动态交互式的数据可视化应用。一、阿里云Atlas地区选择器简介阿里云Atlas是阿里云的一款数据可视化产品…...

编程日记 2025/8/21 16:16:45

尚硅谷TS快速入门笔记（个人笔记用）

TypeScript 快速上手 🪩 禹神：三小时快速上手TypeScript，TS速通教程_哔哩哔哩_bilibili ⼀、TypeScript 简介 TypeScript 由微软开发,是基于 JavaScript 的⼀个扩展语⾔。 TypeScript 包含了 JavaScript 的所有内容,即: TypeScript 是 Jav…...

编程日记 2025/8/21 2:53:27

python: DDD+ORM using oracle 21c

sql script: create table GEOVINDU.School --創建表 ( SchoolId char(5) NOT NULL, -- SchoolName nvarchar2(500) NOT NULL, SchoolTelNo varchar(8) NULL, PRIMARY KEY (SchoolId) --#主鍵 );create table GEOVINDU.Teacher ( TeacherId char(5) NOT NULL , TeacherFirstNa…...

编程日记 2025/8/19 6:49:50

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

一、算法原理与实现

1. 冒泡排序

2. 选择排序

3. 插入排序

4. 希尔排序

5. 归并排序

6. 快速排序

7. 堆排序

8. 基数排序

二、测试公共代码

二、综合对比分析

三、性能优化建议

相关文章：