数据结构(十七):排序算法
排序算法的分类
内部排序:将数据储存在内部存储器中进行排序
插入排序:直接插入排序
希尔排序
选择排序:简单选择排序
堆排序
交换排序:冒泡排序
快速排序
归并排序
基数排序
外部排序,数据量太大,借助外部存储排序
度量算法性能的两种方法
事后统计、事前估算(算法复杂度)
时间频度:一个算法中语句被执行的次数T(n)
时间复杂度:T(n)/f(nn)=O(f(n))
时间复杂度计算方法:用常数1代替所有加法常数、修改后的运行次数函数中只保留最高阶、去除最高项系数
空间复杂度是对存储空间的度量