惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

D
Docker
I
InfoQ
L
LangChain Blog
阮一峰的网络日志
阮一峰的网络日志
Y
Y Combinator Blog
博客园_首页
Martin Fowler
Martin Fowler
宝玉的分享
宝玉的分享
A
About on SuperTechFans
Apple Machine Learning Research
Apple Machine Learning Research
Vercel News
Vercel News
T
The Blog of Author Tim Ferriss
C
Check Point Blog
B
Blog RSS Feed
Cyber Security Advisories - MS-ISAC
Cyber Security Advisories - MS-ISAC
Engineering at Meta
Engineering at Meta
B
Blog
爱范儿
爱范儿
Stack Overflow Blog
Stack Overflow Blog
aimingoo的专栏
aimingoo的专栏
WordPress大学
WordPress大学
F
Fortinet All Blogs
月光博客
月光博客
GbyAI
GbyAI

博客园 - ________囧丶殇

django系列 - 安装和新建项目 SQL - 基础 javascript刷新父页面 SQL - 约束 C语言(8) - 反转单向链表 C语言(7) - 数据结构之单向链表 C语言(5) - 选择排序 快速排序 C语言(4) - 插入排序 C语言(3) - 冒泡排序 归并排序 C语言(2) - 从指针开始 C语言(1) - 开始之前 python实践 - 抓取网页中的图片和数据 python实践 - 下载文件 python补充(2) - 内置函数 python补充(1) python笔记(十) - 异常和文件处理 python笔记(九) - 类 part2 python笔记(八) - 类 part1 python笔记(七) - and和or
C语言(6) - 各种排序算法的比较
________囧丶殇 · 2009-06-09 · via 博客园 - ________囧丶殇

主要测试代码:

int main(void)
{
    PrintDesc();
    
//cal_time(p_func_arr, ARRAY_SIZE(p_func_arr));
    clock_t t_start;   /* start time when test starts */
    clock_t t_end;     
/* end time when test ends */

    t_start 

= clock(); /* get start time */
    
int k = 0;
    
while (k++<ForTimes)
    {
        
int *array = get_ran();
        Sort(array);
    }
    t_end 
= clock();   /* get end time */
    printf(
"数据量:%d ,循环次数:%d ,平均排序时间: %.3f s\n", ArraySize,ForTimes,(double)(t_end-t_start)/(CLOCKS_PER_SEC*ForTimes));return 0;
}

 测试结果:

1. 冒泡排序

---------- C￐L ----------
[冒泡排序]
数据量:
1000 ,循环次数:100 ,平均排序时间: 0.007 s

数据量:

10000 ,循环次数:100 ,平均排序时间: 0.659 s

输出完成 (耗时: 0 秒) 

当测试100000数据量的时候就很慢了,我等到3分钟的时候已经等不下去了,直接CUTE掉了(因为这里是十万数据*100次循环==千万数据了)

冒泡排序是最慢的排序算法。在实际运用中它是效率最低的算法。它通过一趟又一趟地比较数组中的每一个元素,使较大的数据下沉,较小的数据上升。时间复杂度O(n2) 小数据量时使用。

 2.插入排序

---------- C￐L ----------
[插入排序]
数据量:
1000  ,循环次数:100 ,平均排序时间: 0.002 s

数据量:

10000 ,循环次数:100 ,平均排序时间: 0.190 s
输出完成 (耗时: 
0 秒)

 时间复杂度O(n2),小数据量时使用。

3. 选择排序

  ---------- C￐L ----------

[选择排序]
数据量:  
1000 ,循环次数:100 ,平均排序时间: 0.003 s

数据量: 

10000 ,循环次数:100 ,平均排序时间: 0.282 s

输出完成 (耗时: 

0 秒)

 时间复杂度O(n2),小数据量时使用。

4. 快速排序

---------- C￐L ----------
[快速排序]
数据量: 
10000 ,循环次数:100 ,平均排序时间: 0.003 s

数据量:

100000 ,循环次数:100 ,平均排序时间: 0.037 s

数据量:

1000000 ,循环次数:100 ,平均排序时间: 0.420 s
输出完成 (耗时: 
0 秒)

 实际应用中用的最多的,也是最常见的一种排序方法,其主要思想是用了分治法

 时间复杂度O(nlogn)

5. 归并排序

---------- C￐L ----------
[归并排序]
数据量: 
10000 ,循环次数:100 ,平均排序时间: 0.005 s

数据量:

100000 ,循环次数:100 ,平均排序时间: 0.056 s
输出完成 (耗时: 
0 秒)

 数据到达百万的时候会自己CUTE掉

 时间复杂度O(nlogn)

 C排序算法