排序总结
| 算法名 | 简单描述 | 一次运行结果 |
|---|---|---|
| 基数排序 | 假设一堆数字，最高位数为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) | 无关 | 稳定 |
查找总结
| 名称 | 描述 |
|---|---|
| 顺序查找 | 按顺序依次遍历，查找是否存在该元素 |
| 折半查找 | 在有序数组中，每次二分寻找目标值 |
| 分块查找 | 把数据分成多个块，块间存在大小关系，一个块内的值全部大于另一个块。但是块内无序。记录块内最大值。查找时先找到对应块，然后顺序查找 |
| 哈希表查找 | 通过哈希值将内容存到散列中 |
网友评论