NoteDeep

  • 知识点整理

顺序表性能分析

搜索：
平均比较次数ACN(Average Comparing Number)
二分搜索：
平均比较次数
插入和删除：
平均移动次数AMN(Average Moving Number)
插入
删除



栈的应用——利用栈将中缀表达式转化为后缀表达式

算数操作符的栈内栈外优先级

操作符ch
#
（
* / %
+ -
）
栈内优先级isp（in stack priority）
0
1
5
3
6
栈外优先级icp（in coming priority）
0
6
4
2
1
扫描中缀表达式，将之转化为后缀表达式的算法：
初始化后的栈中只有操作符#
重复执行如下操作直到只剩下栈底操作符#
1）若扫描到的是操作数则直接输出，否则转2）
2）若扫描到的是操作符，比较当前操作符的icp与栈顶操作符的isp优先级，若icp>isp当前操作符进栈；若icp<isp弹出栈顶元素到输出序列；若icp==isp弹出栈顶元素但是不输出到输出序列



排序

排序算法的性能评估：排序算法根据数据比较次数和数据移动次数来衡量性能
排序算法的稳定性：在初始序列中a与b序相等，排序后a和b的前后相对位置不变称为稳定

插入排序

直接插入排序：时间复杂度 ，稳定
折半插入排序：时间复杂度 ，稳定
希尔排序：对gap不断减小的gap个子序列（分割、合并然后）进行插入排序，不稳定

交换排序

冒泡排序：时间复杂度 ，稳定
每次遍历都检查一遍序列，若有序则立即停止，则可以只进行一趟排序就得到有序序列

快速排序

选择prior元素，并将小于prior的元素移动到prior左侧，大于prior的元素移动到prior右侧，并不断对prior分割出来的两个子序列进行同样的操作直到排序完成
时间复杂度 ，不稳定

选择排序

直接选择排序
每次都扫描未排序部分，不断选取最大的移至已排序部分的最左侧（或者选取最小的移至已排序部分的最右侧）
时间复杂度 ，不稳定
锦标赛排序
采用树，特别地可以使用完全二叉树，来定义胜者树，每次都对比得出未排序元素中的最大（最小）值
时间复杂度 ，稳定
堆排序（优先队列）
不断对待排序序列进行建堆处理并将堆顶元素放到序列尾端作为已排序部分直到完成排序
时间复杂度 ，不稳定
步骤：（从floor(n/2)开始)自下往上调整成堆，取堆顶，添堆顶，自上往下调整成堆

归并排序

不断将有序的子序列两两合并形成新的子序列，直到排序完成
时间复杂度 ，稳定

分配排序

MSD基数排序：从高位到低位，自上而下排序（不断分组）
LSD基数排序：从低位到高位，自下而上排序（不断分组并收集）
时间复杂度 ，稳定


































评论列表

    顺序表性能分析
    栈的应用——利用栈将中缀表达式转化为后缀表达式
    排序