本帖最后由 dffzh 于 2025-5-6 17:29 编辑
#申请原创#
@21小跑堂
在软件数据处理中，我们会经常使用排序算法先对数据进行降序排序（从大到小）或者升序排序（从小到大）后，再执行进一步处理，比如常见的应用就是采集一定数量的传感器数据后进行排序算法处理。 那你一般都用哪种排序算法呢？有没有遇到数据量多了以后排序算法的执行效率降低的情况？或者有没有研究过不同排序算法之间在执行时间上有什么差别？这篇文章将带你揭晓答案！ 以下将从工作原理，算法步骤，时间复杂度，空间复杂度，稳定性，源代码和仿真验证等方面阐述数据排序算法。 在一般的嵌入式系统中，以下介绍的三种都属于较简单的且性能类似的排序算法，在大多数情况下都可以满足应用需求。
1、冒泡排序算法 工作原理： 通过重复遍历要排序的数据列表，比较相邻的元素并按照升序或降序的要求交换它们的位置来实现。会重复遍历数据列表，直到数据列表已经完成排序操作。 算法步骤： 比较相邻的元素：从列表的第一个元素开始，比较当前元素与下一个元素； 交换位置：如果当前元素比下一元素大（升序排序），则交换它们的位置；降序排序则相反； 重复遍历：对列表的每一对相邻元素重复上述过程，直到列表的末尾；这样，最大（最小）元素就会“冒泡”到列表的最后位置； 缩小范围：忽略已经排序好的最后一个元素，重复上述步骤，直到整个列表排序完成。 时间复杂度： 平均情况：O(n²) 随着数据列表的规模增大，排序工作量将按平方级别的规模变大。 空间复杂度： O(1)（仅需要常数级的内存空间） 稳定性： 因为相等的元素不会交换位置，因此冒泡排序是稳定的排序算法。 源代码： （文章里的代码均以升序排序为例的C代码，读者可参考自行实现降序排序代码）
仿真验证： 先在Visual C++ 6.0软件上验证算法代码的正确性：
然后使用硬件板子在Keil软件上测试了排序100个随机数据的算法执行时间： 这个时间结果并非绝对时间，只是相对时间，与MCU主频有关，我的测试主频是240MHz；
排序100个随机数据的算法执行时间t： t = 18.04128625秒 –18.04077735秒 = 508.9微秒，0.5毫秒左右。
2、选择排序算法 工作原理：每次从待排序的数据列表中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据列表的元素排完。 算法步骤： 初始状态： 无序区为S[0..n-1]，有序区为空； 第i趟排序(i=0,1,2...n-2)开始时，当前有序区和无序区分别为S[0..i-1]和S[i..n-1]； 该趟排序从当前无序区中选出关键值最小的记录S[k]； 将S[k]与无序区的第1个记录S交换；重复以上步骤，共n-1趟，完成排序。 时间复杂度： 平均情况：O(n²)无论数据如何排列，选择排序都需要进行n(n-1)/2次比较。 空间复杂度： O(1)（属于原地排序算法） 稳定性： 交换可能会改变相等元素的相对位置，因此选择排序是不稳定的排序算法。 源代码： 仿真验证： 先在Visual C++ 6.0软件上验证算法代码的正确性： 然后使用硬件板子在Keil软件上测试了排序100个随机数据的算法执行时间： 排序100个随机数据的算法执行时间t： t = 0.14538003秒 – 0.14512233秒= 257.7微秒； 执行速度上比冒泡排序算法快。
3、插入排序算法 工作原理： 每次从无序部分取出一个数据，插入到有序部分的正确位置。 算法步骤： 从数组的第二个元素开始遍历（即索引为1的元素）； 将当前元素与它之前的元素逐一比较，如果当前元素小，则将之前的元素后移； 找到正确的位置后，将当前元素插入到该位置； 重复以上步骤，直到数组遍历完成。 时间复杂度： 平均情况：O(n²) 空间复杂度： O(1)（属于原地排序算法） 稳定性： 插入排序是稳定的排序算法。 源代码： 以下两种实现方法都可以 仿真验证： 先在Visual C++ 6.0软件上验证算法代码的正确性： 然后使用硬件板子在Keil软件上测试了排序100个随机数据的算法执行时间： 排序100个随机数据的算法执行时间t： t = 0.14535409秒 –0.14512319秒 = 230.9微秒； 在执行速度上，三种排序算法的时间分别是508.9微秒、257.7微秒、230.9微秒；即插入排序算法用时最少，执行最快。
从以上对三种常用的简单数据排序算法的阐述和验证上可以得出以下结论：
1、在算法执行速度上，插入排序算法 > 选择排序算法 > 冒泡排序算法，即插入排序算法是简单排序算法里性能较好的一种，值得你拥有； 2、对时间实时性或者响应速度要求不高的场景，三种排序算法你都可以使用； 3、对于有符号数和浮点数类型的操作，在算法上无本质区别，只要修改数据类型即可； 4、对于更高级的嵌入式系统应用，响应时间都是纳秒甚至更高级别，比如航空航天和军事应用等，则可能需要更高效的数据排序算法，比如归并排序算法和快速排序算法，后面文章会更新。
附件有排序算法的源代码pdf文件，可以参考！ | 
楼主
标题置顶
标题高亮
对比测试三种常用的排序算法的执行时间，在执行速度上给出参考，测试效果差异较为明显，结论符合事实。