排序和查找算法
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 条评论
回复 删除
下一页
