排序和查找算法
2024-05-07 10:34:19 0 举报AI智能生成
介绍了常见排序算法的思想和特点。
作者其他创作
大纲/内容
排序
选择排序
找到剩余元素中的最小者并确定其位置。
每次交换都能排定一个元素------交换（移动）次数为N
长度为N的数组，比较N^2 / 2次，交换N次。
运行时间和初始输入状态无关。
插入排序
把每个元素插入到已有序的元素中适当的位置。
平均需要N^2/4次的比较和交换
适用于部分有序的数组，或者元素离最终位置不远的数组。
希尔排序
给间隔为h的元素排序，h以1结尾。
适用于数组较大的情况，子数组用插入排序。
归并排序
递归的分成两半分别排序，再把结果归并起来。
分的时间为lon2n，合的时间为n。 所以平均时间复杂度为n log n
可处理超大数量集，但是也需要额外N的空间
快速排序
原地排序，只需要一个很小的辅助栈。
长度为N的数组，排序所需时间为 NlgN。 递归为lgN
效率和选择的中间值有很大的关系
优先队列
支持 删除最大元素和插入元素两种操作
实现
数组
无序
删除最大元素：类似于选择排序，找到最大值和边界交换然后删除。
查找
无序链表中的顺序查找----比较耗时
有序数组的二分查找
l + (r - l) / 2 这样避免超出越限
递归：不断调用函数
迭代：循环不断减少区间值
不论成功与否：lg N + 1
插入就很麻烦
二分查找树
0 条评论
下一页
