数据结构试讲之排序
插入排序
- 应用:打扑克牌,收试卷,交作业
- 档案整理工作:图书管理工作:
排序问题举例
[2,9,25,16,1,3,100,5],插入排序举例
冒泡排序
- 冒泡排序演示地址
- 时间复杂度分析\((n-1)+(n-2)+... 3+2+1=(n-1+1)*n/2 = 1/2*n^2\) 用计算机的行话就表示O(\(n^2\))
- 做法很傻,跟人肉手动比较一下运行时间
先普及一下CPU主频的知识,3.2G,表示\(3.2*10^9\)次时钟频率,假设,有10万个数字需要你排序,n^2 复杂度.10万*10万=100亿= \(10 * 10^9\) 保守估计,也就5秒钟,就计算完了.我们人类天生是对大量级的数字不敏感的,我们学计算机的就要克服这种现象,凡事都要从量级的角度去考虑问题,不能仅仅局限在几十,几百几千的量级,要把眼光放到几百万,几千万,几十亿这个量级上思考.
- 这个方法,不常用,但是很好理解.而且效果明显.实现起来方便.
快速排序
- 快速排序演示地址
- 跟冒泡排序相比,更不好理解
- 时间复杂度分析\(\underbrace{n+2*\frac{n}{2}+4*\frac{n}{4}}\) 一共有\(log_2^n\)个项,所以结果复杂度为:\(n* log_2^n\)
- 应用,当有全校的档案,10万个数字排序,\(n*log_2^n\) =100万=10^6 按CPU 的主频计算不到0.001秒,就计算完成了,保守估计1000倍的效率,如果同样的一个排序任务冒泡需要15分钟,快速排序只需要10天,才能算完.对比一下这计算差距,才能知道震撼
- 极客学院参考链接,维基百科参考链接
外部排序算法
数据结构需要锻炼的技能
在有限的资源和能力条件下,做出想要的效果.