前言：数据结构第三弹笔记来袭！主要内容为排序、二分查找及跳表。

排序

（1）冒泡、插入、选择排序：时间复杂度O(n^2)，基于比较
快速、归并排序：时间复杂度O(nlogn)，基于比较
桶、计数、基数排序：时间复杂度O(n)，不基于比较
（2）排序算法的执行效率：
最好情况、最坏情况、平均情况时间复杂度；时间复杂度的系数、常数 、低阶；比较次数和交换（或移动）次数
（3）排序算法的内存消耗：原地排序
（4）排序算法的稳定性：前后顺序不发生变化
（5）冒泡排序：冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。
（6）冒泡排序的空间复杂度为 O(1)，是一个原地排序算法，相同元素不交换时是稳定的排序算法。最好情况时间复杂度是 O(n)。而最坏的情况是，要排序的数据刚好是倒序排列的，我们需要进行n次冒泡操作，所以最坏情况时间复杂度为 O(n^2)。
（7）“有序度”和“逆序度”。有序度是数组中具有有序关系的元素对的个数。完全有序的数组的有序度叫作满有序度。逆序度 = 满有序度 - 有序度。
（8）插入排序：将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。
（9）插入排序的空间复杂度为 O(1)，是一个原地排序算法，相同元素放后面时是稳定的排序算法。最好情况时间复杂度是 O(n)，最坏情况时间复杂度为 O(n^2)。
（10）选择排序：选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。
（11）选择排序空间复杂度为O(1)，是一种原地排序算法。选择排序的最好情况时间复杂度、最坏情况和平均情况时间复杂度都为 O(n^2)。

归并排序与快速排序

（1）归并排序：归并排序的核心思想还是蛮简单的。如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。使用的就是分治思想。
（2）归并排序是稳定的排序算法，利用tmp数组。归并排序的时间复杂度是 O(nlogn)，空间复杂度就是 O(n)。
（3）快速排序：如果要排序数组中下标从 p 到 r 之间的一组数据，我们选择 p 到 r 之间的任意一个数据作为 pivot（分区点）。我们遍历 p 到 r 之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot 放到中间。经过这一步骤之后，数组 p 到 r 之间的数据就被分成了三个部分，前面 p 到 q-1 之间都是小于 pivot 的，中间是 pivot，后面的 q+1 到 r 之间是大于 pivot 的。merge()合并函数。partition()分区函数。
（4）归并排序的处理过程是由下到上的，先处理子问题，然后再合并。而快排正好相反，它的处理过程是由上到下的，先分区，然后再处理子问题。归并排序虽然是稳定的、时间复杂度为 O(nlogn) 的排序算法，但是它是非原地排序算法。我们前面讲过，归并之所以是非原地排序算法，主要原因是合并函数无法在原地执行。快速排序通过设计巧妙的原地分区函数，可以实现原地排序，解决了归并排序占用太多内存的问题。
（5）快排思想在O(n)可用于查找第K大元素

线性排序

（1）桶排序（Bucket sort）:核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。
（2）桶排序在极端情况下，如果数据都被划分到一个桶里，那就退化为 O(nlogn) 的排序算法了。桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。
（3）计数排序（Counting sort）：计数排序其实是桶排序的一种特殊情况。当要排序的 n 个数据，所处的范围并不大的时候，比如最大值是 k，我们就可以把数据划分成 k 个桶。每个桶内的数据值都是相同的，省掉了桶内排序的时间。计数排序只能用在数据范围不大的场景中，如果数据范围 k 比要排序的数据 n 大很多，就不适合用计数排序了。而且，计数排序只能给非负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整数。
（4）基数排序（Radix sort）：对要排序的数据是有要求的，需要可以分割出独立的“位”来比较，而且位之间有递进的关系，如果 a 数据的高位比 b 数据大，那剩下的低位就不用比较了。除此之外，每一位的数据范围不能太大，要可以用线性排序算法来排序，否则，基数排序的时间复杂度就无法做到 O(n) 了。
（5）线性排序可应用于年龄给100万用户数据排序

排序优化问题

（1）如何实现一个通用的、高性能的排序函数
（2） 排序时间复杂度和特征结论
时间复杂度 是稳定排序 是原地排序
冒泡排序 O(n^2) √ √
插入排序 O(n^2) √ √
选择排序 O(n^2) × √
快速排序 O(nlogn) × √
归并排序 O(nlogn) √ ×
计数排序 O(n+k) k是数据范围 √ ×
桶排序 O(n) √ ×
基数排序 O(dn) d是维度 √ ×
（2）如果对小规模数据进行排序，可以选择时间复杂度是 O(n2) 的算法；如果对大规模数据进行排序，时间复杂度是 O(nlogn) 的算法更加高效。所以，为了兼顾任意规模数据的排序，一般都会首选时间复杂度是 O(nlogn) 的排序算法来实现排序函数。
使用归并排序的情况其实并不多。我们知道，快排在最坏情况下的时间复杂度是 O(n^2)。
（3）优化快速排序：最理想的分区点是：被分区点分开的两个分区中，数据的数量差不多。
三数取中法：我们从区间的首、尾、中间，分别取出一个数，然后对比大小，取这 3 个数的中间值作为分区点。这样每间隔某个固定的长度，取数据出来比较，将中间值作为分区点的分区算法，肯定要比单纯取某一个数据更好。但是，如果要排序的数组比较大，那“三数取中”可能就不够了，可能要“五数取中”或者“十数取中”。
随机法：随机法就是每次从要排序的区间中，随机选择一个元素作为分区点。

二分查找

（1）二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。
（2）二分查找时间复杂度为 O(logn)。
（3）二分查找的递归与非递归实现。最简单的情况就是有序数组中不存在重复元素。循环实现，容易出错的 3 个地方：循环退出条件，mid 的取值，low 和 high 的更新。递归实现。
（4）二分查找应用场景的局限性：查找依赖的是顺序表结构，简单点说就是数组。二分查找针对的是有序数据。数据量太小或者太大都不适合二分查找。
（5）二分查找的4种常见变形问题：查找第一个值等于给定值的元素、查找最后一个值等于给定值的元素、查找第一个大于等于给定值的元素、查找最后一个小于等于给定值的元素。
（6）快速定位出一个 IP 地址的归属地：IP 地址可以转化为 32 位的整型数。所以，我们可以将起始地址，按照对应的整型值的大小关系，从小到大进行排序。然后问题可以转化为第4种变形问题“在有序数组中，查找最后一个小于等于某个给定值的元素”
（7）凡是用二分查找能解决的，绝大部分我们更倾向于用散列表或者二叉查找树。求“值等于给定值”的二分查找确实不怎么会被用到，二分查找更适合用在“近似”查找问题，在这类问题上，二分查找的优势更加明显。比如今天讲的这几种变体问题，用其他数据结构，比如散列表、二叉树，就比较难实现了。
（8）变体的二分查找算法很容易因为细节处理不好而产生Bug，容易出错的细节有：终止条件、区间上下界更新方法、返回值选择。

跳表

（1）跳表：对链表稍加改造，加入多级索引的结构，支持类似“二分”的查找算法。它是一种各方面性能都比较优秀的动态数据结构，可以支持快速的插入、删除、查找操作，写起来也不复杂，甚至可以替代红黑树（Red-black tree）。
（2）跳表实现：对链表建立一级“索引”，例如每两个结点提取一个结点到上一级，我们把抽出来的那一级叫作索引或索引层。索引下的down表示down 指针，指向下一级结点。
（3）在跳表中查询任意数据的时间复杂度就是 O(logn)，空间复杂度是 O(n)。
（4）跳表这个动态数据结构，不仅支持查找操作，还支持动态的插入、删除操作，而且插入、删除操作的时间复杂度也是 O(logn)。
（5）跳表索引动态更新，当我们不停地往跳表中插入数据时，如果我们不更新索引，就有可能出现某 2 个索引结点之间数据非常多的情况。极端情况下，跳表还会退化成单链表。因此，我们需要某种手段来维护索引与原始链表大小之间的平衡，也就是说，如果链表中结点多了，索引结点就相应地增加一些，避免复杂度退化，以及查找、插入、删除操作性能下降。
（6）Redis要用跳表来实现有序集合，而不是红黑树的原因：
Redis中的有序集合支持的核心操作，插入一个数据；删除一个数据；查找一个数据；按照区间查找数据（比如查找值在 [100, 356] 之间的数据）；迭代输出有序序列。
插入、删除、查找以及迭代输出有序序列这几个操作，红黑树也可以完成，时间复杂度跟跳表是一样的。但是，按照区间来查找数据这个操作，红黑树的效率没有跳表高。跳表的缺点就是暂时没有现成的实现。红黑树较多。