算法与数据结构 TopK问题 全局排序 局部排序 堆 分治法 减治法 随机选择 排序 选择排序 简单选择排序 Selection Sort 稳定性 不稳定 时间复杂度 O(n2) 工作原理 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾 堆排序Heap Sort 分支主题 交换排序 快速排序Quick Sort） 思想 通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序 冒泡排序 Bubble Sort 归并排序Merge Sort） 稳定性 稳定 时间复杂度 O(nlogn） 工作原理 采用分治法（Divide and Conquer 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序 计数排序Counting Sort 稳定性 稳定 时间复杂度 O(n+k) 工作原理 采用分治法（Divide and Conquer 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序 基数排序 桶排序 复杂度为O(n) 插入排序 简单插入排序 Insertion Sort 时间复杂度 O(n2) 稳定性 稳定 工作原理 通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入 希尔排序 缩小增量排序 稳定性 不稳定 时间复杂度 O(n1.3) 工作原理 数1问题 位移法 求与法 n&(n-1) 斐波那契数列f(n) 递归法 正推法 通项公式法 f(n)=(1/√5){[(1+√5)/2]^n -[(1-√5)/2]^n} 查表法 时间复杂度 第一大类，简单规则 规则一：“有限次操作”的时间复杂度往往是O(1) 规则二：“for循环”的时间复杂度往往是O(n) 规则三：“树的高度”的时间复杂度往往是O(lg(n)) 二分查找的时间复杂度是O(lg(n)) 快速排序的时间复杂度n(lg(n)) 第二大类：组合规则 通过简单规则的时间复杂度，来求解组合规则的时间复杂度 第三大类，递归求解 数据结构 树 二叉树 堆 链表 广义表 线性表 哈希表 图 二叉树 数据一致性算法 paxos hhash