冒泡、插入、选择、归并排序的C语言实现

冒泡、插入、选择、归并排序的C语言实现

注意：本文是小白文，大神请轻喷，热烈欢迎指导，特别声明，本文是划水文，不是学术研究，极可能存在谬误，如果拿去吹牛，出现被打脸的情况，本人概不负责。

本文是对冒泡、插入、选择、归并排序的C语言实现，以及不做任何优化情况下，特定数据规模下的排序时间对比-体验空间换时间在排序速度上的巨大影响。

我们知道，冒泡，插入和选择排序，都是原地排序算法，不需要申请额外的存储空间，就可以完成排序，他的时间复杂度是O(n2)；
归并排序，是非原地排序算法，他需要额外的存储空间辅助进行排序，它的时间复杂度是O(nlogn)。

至于对某种算法是不是稳定排序算法的判定，我一直认为，这个不是算法本身决定的，而是你的实现细节决定的。一种算法，可以实现成稳定排序，也可以实现成不稳定排序。

在极小的数据规模下，上述四种算法，并不能比较出优劣，至于程序员们常说的，用空间换时间，到底能有多大效果，也不能有个直观的体会。

本文用c语言，分别实现了上述四种算法，都是按照理解手扣的，特别想提的是，在实现归并算法的时候，没有用迭代，而是按照最直接的理解，自己实现的，从我个人的思维习惯上来讲，这个写法，更容易理解，具体归并过程，见下图：

跟大神们实现思路略有不同，不知道理解上有没有偏差。

为了测试效果，本人对500590个byte长度的全英文书籍内容，也就是10万级别的数据规模进行排序，发用时间换空间的归并排序，比剩余三种时间复杂度为O(n2)的排序算法，快出n个数量级别，即使在不同硬件情况电脑上跑出的具体结果不同，但是数量级的区别应该能体现出来。

算法时间消耗（毫秒）冒泡1747805（将近半个小时）插入476832（不到8分钟）选择310672（5分钟出头）归并76（是的，76毫秒。。。）

由上可以看出，即使是同样时间复杂度的算法，在实现细节上的不同和数据集合有序度等多重作用的影响下，在实际应用中也能差出比较大的差距。

代码仓库地址

shell 运行记录

fozei@fozei-PC:~/code/c-cpp/c$ ./doSort -b 12
argc is 3
argv[0] is ./doSort
argv[1] is -b
do bubble
file size is = 500590
time consumed = 1747805
fozei@fozei-PC:~/code/c-cpp/c$ ./doSort -m 12
argc is 3
argv[0] is ./doSort
argv[1] is -m
do merge
file size is = 500590
time consumed = 73
fozei@fozei-PC:~/code/c-cpp/c$ ./doSort -m 12
argc is 3
argv[0] is ./doSort
argv[1] is -m
do merge
file size is = 500590
time consumed = 73
fozei@fozei-PC:~/code/c-cpp/c$ ./doSort -m 12
argc is 3
argv[0] is ./doSort
argv[1] is -m
do merge
file size is = 500590
time consumed = 73
fozei@fozei-PC:~/code/c-cpp/c$ ./doSort -m 12
argc is 3
argv[0] is ./doSort
argv[1] is -m
do merge
file size is = 500590
time consumed = 73
fozei@fozei-PC:~/code/c-cpp/c$ ./doSort -m 12
argc is 3
argv[0] is ./doSort
argv[1] is -m
do merge
file size is = 500590
time consumed = 75
fozei@fozei-PC:~/code/c-cpp/c$ ./doSort -b 12
argc is 3
argv[0] is ./doSort
argv[1] is -b
do bubble
file size is = 500590
time consumed = 1730653
fozei@fozei-PC:~/code/c-cpp/c$ ./doSort -i 12
argc is 3
argv[0] is ./doSort
argv[1] is -i
do insert
file size is = 500590
time consumed = 476832
fozei@fozei-PC:~/code/c-cpp/c$ ./doSort -s 12
argc is 3
argv[0] is ./doSort
argv[1] is -s
do selection
file size is = 500590
time consumed = 310672
fozei@fozei-PC:~/code/c-cpp/c$ ./doSort -m 12
argc is 3
argv[0] is ./doSort
argv[1] is -m
do merge
file size is = 500590
time consumed = 76