牛客网刷题

排序+查找总结

2018-10-12  本文已影响7人  闭门造折

排序总结

算法名 简单描述 一次运行结果
基数排序 假设一堆数字,最高位数为n,首先对个位进行排序,按顺序排好后,再按十位进行排序,依次最终对第n为进行排序,此时所有数字有序 数字按个位数字和固有顺序排列
插入排序 每次选取一个数字,插入到前面已经排好序的数字串中 前两个数有序
快速排序 选定的数,先从后往前找比他小的数,交换位置,再从前往后找比他大的数,交换位置,直到他两侧的数字以他为分界,分别大于或小于他(等于的情况应具体归类于左侧或右侧一侧中) 数组第1个数作为选定的数,此时出现在整个数组中间
希尔排序 选定一个n,第1项和第n+1项排序,第2项和第n+2项排序,...一遍排序后,将n缩小1,重复这个操作,直到n=1。有的题目是从后往前逐步排序 间隔为n的框边缘元素依次有序(也可能无序,因为一个位置可能被交换两次)
堆排序 构建一个二叉树,初始化的时候从最左非叶节点开始,每次把非叶节点的值和整个子树中,局部最大(先判断左右叶子那个大,选大的走,不断递归)的节点交换。之后逐步往上重复这个操作。全部操作完后,每次选择数组最末尾数字和堆顶元素,并把堆顶节点执行以下节点交换操作。参考博客《图解排序算法(三)之堆排序》
归并排序 初始是n个小集合,每次两两凑成一个大集合,logn次之后,全部形成一个有序集合。 一堆集合,每个集合中有2个已排序元素
选择排序 每次选择最大/最小的放到最开始 第一个数是正确的,其他不动
冒泡排序 相邻两个数比较+排序,从头向尾递归,每次能得到准确的最后一个数 最后一个数正确,前面的数部分出现移动
算法名 时间复杂度 最坏时间 最好时间 空间复杂度 与初始位置 稳定性
基数排序 O(d(n+r)) O(d(n+r)) O(d(n+r)) O(r) 无关 稳定
插入排序 O(n^2) O(n^2) O(n) O(1) 有关 稳定
快速排序 O(nlogn) O(n^2) O(nlogn) O(nlogn) 有关 不稳定
希尔排序 O(n^1.3) 存在多种 存在多种 O(1) 无关 不稳定
堆排序 O(nlogn) O(nlogn) O(nlogn) O(1) 不稳定
归并排序 O(nlogn) O(nlogn) O(nlogn) O(n) 无关 稳定
选择排序 O(n^2) O(n^2) O(n^2) O(1) 无关 不稳定
冒泡排序 O(n^2) O(n^2) O(n) O(1) 无关 稳定

查找总结

名称 描述
顺序查找 按顺序依次遍历,查找是否存在该元素
折半查找 在有序数组中,每次二分寻找目标值
分块查找 把数据分成多个块,块间存在大小关系,一个块内的值全部大于另一个块。但是块内无序。记录块内最大值。查找时先找到对应块,然后顺序查找
哈希表查找 通过哈希值将内容存到散列中
上一篇 下一篇

猜你喜欢

热点阅读