数据结构与算法之美（二）

递归

递归需要满足的三个条件

一个问题的解可以分解为几个子问题的解
何为子问题？子问题就是数据规模更小的问题。
这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
存在递归中止条件
把问题分解为子问题，把子问题再分解为子子问题，一层一层分解下去，不能存在无限循环，这就需要有终止条件。

如何编写递归代码

写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码。

如果一个问题A可以分解为若干子问题B、C、D，你可以假设子问题B、C、D已经解决，在此基础上思考如何解决问题A。而且，你只需要思考问题A与子问题B、C、D两层之间的关系即可，不需要一层一层往下思考子问题与子子问题，子子问题与子子子问题之间的关系。屏蔽掉递归细节，这样子理解起来就简单多了。

因此，编写递归代码的关键是，只要遇到递归，我们就把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤。

递归代码要警惕重复计算

为了避免重复计算，我们可以通过一个数据结构（比如散列表）来保存已经求解过的f(k)。当递归调用到f(k)时，先看下是否已经求解过了。如果是，则直接从散列表中取值返回，不需要重复计算，这样就能避免刚讲的问题了。

排序

最经典的、最常用的：冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序。

如何分析一个“排序算法”

排序算法的执行效率
1. 最好情况、最坏情况、平均情况时间复杂度
  为啥要区分这三种时间复杂度呢？第一、有些排序算法会区分，为了好对比，所以我们最好都做一下区分。第二，对于要排序的数据，有的接近有序，有的完全无序。有序度不同的数据，对于排序的执行时间肯定是有影响的，我们要知道排序算法在不同数据下的性能表现。
2. 时间复杂度的系数、常熟、低阶
  在对同一阶时间复杂度的排序算法性能对比的时候，我们就要把系数、常数、低阶也考虑进来。
3. 比较次数和交换（或移动）次数
  基于比较的排序算法的执行过程，会涉及到两种操作，一种是元素比较大小，另一种是元素交换或移动。所以，如果我们在分析排序算法的执行效率的时候，应该把比较次数和交换（或移动）次数也考虑进去。
排序算法的内存消耗
算法的内存消耗可以通过空间复杂度来衡量。原地排序算法。就是特指空间复杂度是O(1)的排序算法。
排序算法的稳定性
稳定性：如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。

冒泡排序

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复n次，就完成了n个数据的排序工作。

当某次冒泡操作已经没有数据交换时，说明已经达到完全有序，不用再继续执行后续的冒泡操作。

public void bubbleSort(int[] a, int n)
{
    if (n <= 1) return;

    for (int i = 0; i < n; n++)
    {
        // 提前退出冒泡循环的标志位
        bool flag = false;
        for (int j = 0; j < n - i - 1; ++j)
        {
            if (a[j] > a[j + 1])
            {
                int tmp = a[j];
                a[j + 1] = tmp;
                flag = true;// 表示有数据交换
            }
        }
        if (!flag) break; // 没有数据交换，提前退出
    }
}

冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为O(1)，是一个原地排序算法。

在冒泡排序中，只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性，当有相邻的两个元素大小相等的时候，我们不做交换，相同大小的数据在排序前后不会改变顺序，所以冒泡排序是稳定的排序算法。

最好情况下，要排序的数据已经是有序的了，我们只需要进行一次冒泡操作，就可以结束了，所以最好情况时间复杂度是O(n)。而最坏的情况是，要排序的数据刚好是倒序排列的，我们需要进行n次冒泡操作，所以最坏情况时间复杂度为O(n2)。

插入排序

首先，我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。

public void insertionSort(int[] a, int n)
{
    if(n<=1) return;
    for(int i = 1;i<n;++i)
    {
        int value = a[i];
        int j = i-1;
        // 查找插入的位置
        for(; j>=0;--j)
        {
            if(a[j]>value)
            {
                a[j+1] = a[j]; // 数据移动
            }else{
                break;
            }
        }
        a[j+1] = value;// 插入数据
    }
}

插入排序算法的运行并不需要额外的存储空间，所以空间复杂度是O(1)，也就是说，这是一个原地排序算法。

在插入排序中，对于值相同的元素，我们可以选择将后面出现的元素，插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变，所以插入排序是稳定的排序算法。

如果要排序的数据已经是有序的，我们并不需要搬移任何数据。如果我们从尾到头在有序数据组里面查找插入位置，每次只需要比较一个数据就能确定插入的位置。所以这种情况下，最好是时间复杂度为O(n)。注意，这里是从尾到头遍历已经有序的数据。

如果数组是倒序的，每次插入都相当于在数组的第一个位置插入新的数据，所以需要移动大量的数据，所以最坏情况时间复杂度为O(n2)。

还记得我们在数组中插入一个数据的平均时间复杂度是多少吗？没错，是O(n)。所以，对于插入排序来说，每次插入操作都相当于在数组中插入一个数据，循环执行n次插入操作，所以平均时间复杂度为O(n2)。

选择排序

选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。

选择排序空间复杂度为O(1)，是一种原地排序算法。选择排序的最好情况时间复杂度、最坏情况和平均情况时间复杂度都为O(n2)。

选择排序是一种不稳定的排序算法。选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性。

归并排序

归并排序的核心思想，如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再把排好序的两部分合并在一起，这样整个数组就都有序了。

归并排序使用的就是分治思想。分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。小的子问题解决了，大的问题也就解决了。

归并排序是一个稳定的排序算法。

归并排序的执行效率与要排序的原始数组的有序程度无关，所以其时间复杂度是非常稳定的，不管是最好情况、最坏情况，还是平均情况，时间复杂度都是O(nlogn)。

空间复杂度是O(n)。

快速排序

快排的思想是这样的：如果要排序数组中的下标从p到r之间的一组数据，我们选择p到r之间的任意一个数据作为pivot（分区点）。我们遍历p到r之间的数据，将小于pivot的放到左边，将大于pivot的放到右边，将pivot放到中间。经过这一步骤之后，数组p到r之间的数据就被分成了三个部分，前面p到q-1之间都是小于pivot的，中间是pivot，后面的q+1到r之间是大于pivot的。根据分治、递归的处理思想，我们可以用递归排序下标从p到q-1之间的数据和下标从q+1到r之间的数据，直到区间缩小为1，就说明所有的数据都有序了。

快速排序不是一个稳定的排序算法。时间复杂度O(nlog n),空间复杂度O(1)。

桶排序

桶排序，顾名思义，会用到“桶”，核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。

桶排序的时间复杂度是O(n)。

桶排序对排序数据的要求

要排序的数据需要和容易就能划分成m个桶，并且，桶与桶之间有着天然的大小顺序。这样每个桶内的数据都排序完之后，桶与桶之间的数据不需要再进行排序。
其次，数据在各个桶之间的分布是比较均匀的。如果数据经过桶的划分之后，有些桶里的数据非常多，有些非常少，很不平均，那桶内数据排序的时间复杂度就不是常量级了。在极端情况下，如果数据都被划分到一个桶里，那就退化为O(nlog n)的排序算法了。
桶排序比较适合用在外部排序中。

计数排序

计数排序其实是桶排序的一种特殊情况。当要排序的n个数据，所处的范围并不大的时候，比如最大值是k，我们就可以把数据划分成k个桶，每个桶内的数据值都是相同的，省掉了桶内排序的时间。

代码逻辑如下：

public void CountingSort(int[] a, int n)
{
    if (n <= 1) return;
    // 查找数组中数据的范围
    var max = a[0];
    for (var i = 1; i < n; ++i)
    {
        if (max < a[i])
        {
            max = a[i];
        }
    }
    var c = new int[max + 1]; // 申请一个计数数组c，下标大小[0,max]
    for (var i = 0; i <= max; ++i)
    {
        c[i] = 0;
    }
    // 计算每个元素的个数，放入c中
    for (var i = 0; i < n; ++i)
    {
        c[a[i]]++;
    }
    // 依次累加
    for (var i = 1; i <= max; ++i)
    {
        c[i] = c[i - 1] + c[i];
    }
    // 临时数组r，存储排序之后的结果
    var r = new int[n];
    // 计算排序的关键步骤，有点难理解
    for (var i = n - 1; i >= 0; --i)
    {
        var index = c[a[i]] - 1;
        r[index] = a[i];
        c[a[i]]--;
    }
    // 将结果拷贝给a数组
    for (var i = 0; i < n; ++i)
    {
        a[i] = r[i];
    }
}

计数排序只能用在数据范围不大的场景中，如果数据范围k比要排序的数据n大很多，就不适合用计数排序了。而且，计数排序只能给非负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整数。

基数排序

基数排序对要排序的数据是有要求的，需要可以分割出独立的“位”来比较，而且位之间有递进的关系，如果a数据的高位比b数据大，那剩下的低位就不用比较了。除此之外，每一位的数据范围不能太大，要可以用线性排序算法来排序，否则，基数排序的时间复杂度就无法做到O(n)了。

如何实现一个通用的、高性能的排序函数

如何选择合适的排序算法？

	时间复杂度	是否稳定排序	是否原地排序
冒泡排序	O(n^2)	√	√
插入排序	O(n^2)	√	√
选择排序	O(n^2)	×	√
快速排序	O(nlogn)	×	√
归并排序	O(nlogn)	√	×
计数排序	O(n+k)	√	×
桶排序	O(n)	√	×
基数排序	O(dn)	√	×

如果对小规模数据进行排序，可以选择时间复杂度是O(n2)的算法；如果对大规模数据进行排序，时间复杂度是O(nlogn)的算法更加高效。所以，为了兼顾任意规模数据的排序，一般都会首选时间复杂度是O(nlogn)的排序算法来实现排序函数。

如何优化快速排序？

三数取中法
我们从区间的首、尾、中间，分别取出一个数，然后对比大小，取这3个数的中间值作为分区点。这样每间隔某个固定的长度，取数据出来比较，将中间值作为分区点的分区算法，肯定要比单纯取某一个数据更好。但是，如果要排序的数组比较大，那“三数取中”可能就不够了，可能要“五数取中”或者“十数取中”。
随机法
随机法就是每次从要排序的区间中，随机选择一个元素作为分区点。这种方法并不能保证每次分区点都选的比较好，但是从概率的角度来看，也不大可能会出现每次分区点都选的很差的情况，所以平均情况下，这样选的分区点是比较好的。时间复杂度退化为最糟糕的O(n2)的情况，出现的可能性不大。

二分查找

二分思想：每次都与区间的中间数据比对大小，缩小查找区间的范围。

二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为0。时间复杂度是O(logn)。

最简单的二分查找算法实现

public static int BsSearch(int[] a, int n, int value)
{
    var low = 0;
    var high = n - 1;
    while (low<=high)
    {
        var mid = low + (high - low) / 2;
        if (a[mid] == value)
        {
            return mid;
        }
        else if(a[mid] < value)
        {
            low = mid + 1;
        }
        else
        {
            high = mid - 1;
        }
    }
    return -1;
}

容易出错的3个地方

循环退出条件
注意是low<=high，而不是low < high。
mid的取值
mid=(low+high)/2这种写法是有问题的。因为如果low+high比较大的话，两者之和就有可能会溢出。改进的方法是将mid的计算方式写成low+(high-low)/2。
low和high的更新
low=mid+1，high=mid-1。注意这里的+1和-1，如果直接写成low=mid或者high=mid，就可能会发生死循环。

二分查找应用场景的局限性

二分查找依赖的是顺序表结构，简单点说就是数组。
二分查找针对的是有序数据。
二分查找只能用在插入、删除操作不频繁，一次排序多次查找的场景中。
数据量太小不适合二分查找，数据量太大也不适合二分查找。

4种常见的二分查找变形问题

查找第一个值等于给定值的元素

a[mid]跟要查找的value的大小关系有三种情况：大于、小于、等于。对于a[mid]>value的情况，我们需要更新high= mid-1；对于a[mid]<value的情况，我们需要更新low=mid+1。

如果mid等于0，那这个元素已经是数组的第一个元素，那它肯定是我们要找的；如果mid不等于0，但a[mid]的前一个元素a[mid-1]不等于value，那也说明a[mid]就是我们要找的第一个值等于给
定值的元素。

如果经过检查之后发现a[mid]前面的一个元素a[mid-1]也等于value，那说明此时的a[mid]肯定不是我们要查找的第一个值等于给定值的元素。那我们就更新high=mid-1，因为要找的元素肯定出现在[low, mid-1]之间。

public static int BsSearchFirstEqual(int[] a, int n, int value)
{
    var low = 0;
    var high = n - 1;
    while (low <= high)
    {
        var mid = low + ((high - low) >> 1);
        if (a[mid] > value)
        {
            high = mid - 1;
        }
        else if (a[mid] < value)
        {
            low = mid + 1;
        }
        else
        {
            if (mid == 0 || a[mid - 1] != value)
                return mid;
            high = mid - 1;
        }
    }
    return -1;
}

查找最后一个值等于给定值的元素

如果a[mid]这个元素已经是数组中的最后一个元素了，那它肯定是我们要找的；如果a[mid]的后一个元素a[mid+1]不等于value，那也说明a[mid]就是我们要找的最后一个值等于给定值的元素。

如果我们经过检查之后，发现a[mid]后面的一个元素a[mid+1]也等于value，那说明当前的这个a[mid]并不是最后一个值等于给定值的元素。我们就更新low=mid+1，因为要找的元素肯定出现在[mid+1, high]之间。

public static int BsSearchLastEqual(int[] a, int n, int value)
{
    var low = 0;
    var high = n - 1;
    while (low <= high)
    {
        var mid = low + ((high - low) >> 1);
        if (a[mid] > value)
        {
            high = mid - 1;
        }
        else if (a[mid] < value)
        {
            low = mid + 1;
        }
        else
        {
            if (mid == n - 1 || a[mid + 1] != value)
                return mid;
            low = mid + 1;
        }
    }
    return -1;
}

查找第一个大于等于给定值的元素

如果a[mid]小于要查找的值value，那要查找的值肯定在[mid+1, high]之间，所以，我们更新low=mid+1。

对于a[mid]大于等于给定值value的情况，我们要先看下这个a[mid]是不是我们要找的第一个值大于等于给定值的元素。如果a[mid]前面已经没有元素，或者前面一个元素小于要查找的值value，那a[mid]就是我们要找的元素。

如果a[mid-1]也大于等于要查找的值value，那说明要查找的元素在[low, mid-1]之间，所以，我们将high更新为mid-1。

public static int BsSearchFirstEqualOrGreater(int[] a, int n, int value)
{
    var low = 0;
    var high = n - 1;
    while (low <= high)
    {
        var mid = low + ((high - low) >> 1);
        if (a[mid] >= value)
        {
            if (mid == 0 || a[mid - 1] < value)
            {
                return mid;
            }

            high = mid - 1;
        }
        else
        {
            low = mid + 1;
        }
    }
    return -1;
}

查找最后一个小于等于给定值的元素

如果a[mid]大于要查找的值value，那要查找的值肯定在[0, mid-1]之间，所以，我们更新high=mid-1。

对于a[mid]小于等于给定值value的情况，我们要先看下这个a[mid]是不是我们要找的最后一个值小于等于给定值的元素。如果a[mid]后面已经没有元素，或者后面一个元素大于要查找的值value，那a[mid]就是我们要找的元素。

如果a[mid+1]也小于等于要查找的值value，那说明要查找的元素在[mid+1, high]之间，所以，我们将low更新为mid+1。

public static int BsSearchLastEqualOrLess(int[] a, int n, int value)
{
    var low = 0;
    var high = n - 1;
    while (low <= high)
    {
        var mid = low + ((high - low) >> 1);
        if (a[mid] <= value)
        {
            if (mid == n - 1 || a[mid + 1] > value)
            {
                return mid;
            }
            low = mid + 1;
        }
        else
        {
            high = mid - 1;
        }
    }
    return -1;
}

读书笔记

#读书笔记 #技术

数据结构与算法之美（二）

http://blog.chcaty.cn/2021/07/21/shu-ju-jie-gou-yu-suan-fa-zhi-mei-er/

作者

caty

发布于

2021年7月21日

许可协议

数据结构与算法之美（三）上一篇

数据结构与算法之美（一）下一篇