数据结构与算法-递归、排序、二分查找

发表于

递归

什么是递归？

  1. 递归是一种应用非常广泛、非常高效、简洁的算法（或者编码技巧）。很多数据结构和算法的编程实现都要用到递归，比如 DFS 深度优化搜索、前中后序二叉树遍历等。
  2. 方法或函数调用自身的方式称为递归调用，调用称为递，返回称为归。
  3. 所有的递归问题都可以用递推公式来表示。（如：f(n) = f(n - 1) + 1 其中 f(1) = 1)

递归的优缺点？

  • 优点：递归代码的表达力强，写起来非常简洁。
  • 缺点：空间复杂度高、有堆栈溢出的风险、存在重复计算、过多的函数调用会耗时较多。

什么样的问题适合递归？

  1. 一个问题的解可以分解为几个子问题的解
  2. 这个问题与分解之后的子问题，除了数据规模不同，求解的思路完全相同。
  3. 存在递归终止条件，不能无限循环下去

如何实现递归？

  1. 观察分析。找到如何将大问题分解为小问题的规律，写出递推公式，找到终止条件。
  2. 思维方式。对于递归代码，不需要试图去想清楚整个递和归的过程。这样反而会进入思维误区。如果一个问题 A 可以分解为若干子问题 B、C、D，你可以假设子问题 B、C、D 已经解决，在此基础上思考如何解决问题 A。而且，你只需要思考问题 A 与子问题 B、C、D 两层之间的关系即可，不需要一层一层往下思考子问题与子子问题，子子问题与子子子问题之间的关系。

递归常见的问题和解决方案

  1. 递归代码警惕堆栈溢出。在系统资源有限的情况下，如果递归求解的数据规模很大，调用层次很深，就会出现堆栈溢出的风险。我们可以通过在代码中限制递归调用的最大深度的方式来解决这个问题。递归调用超过一定深度（比如 1000）之后，我们就不继续往下再递归了，直接返回报错。
  2. 递归代码警惕重复计算。递归过程中，还可能存在重复计算的问题。可以通过一个数据结构（比如散列表）来保存已经求解过的 f(k)。当递归调用到 f(k) 时，先看下是否已经求解过了。如果是，则直接从散列表中取值返回，避免重复计算。
  3. 在时间效率上，递归代码里多了很多函数调用，当这些函数调用的数量较大时，就会积聚成一个可观的时间成本。
  4. 在空间复杂度上，因为递归调用一次就会在内存栈中保存一次现场数据，所以在分析递归代码空间复杂度时，需要额外考虑这部分的开销。

排序

如何分析一个排序算法

排序算法的执行效率
  1. 最好情况、最坏情况、平均情况时间复杂度。
  2. 时间复杂度的系数、常数、低阶。
  3. 比较次数和交换（或移动）次数。
排序的内存消耗
  1. 原地排序算法：特指空间复杂度是O(1)的排序算法。
排序算法的稳定性
  1. 稳定排序算法：经过排序算法后，值相等的元素前后顺序不发生改变。
  2. 不稳定排序算法：经过排序算法后，值相等的元素前后算许发生变化。

冒泡排序

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

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

代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int[] bubbleSort(int[] arr) {
        
    for (int i = 0; i < arr.length; i++) {

        boolean flag = false;
        for (int j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j + 1];
                arr[j + 1] = arr[j];
                arr[j] = temp;

                flag = true;
            }
        }

        if (!flag) {
            break;
        }

    }
    return arr;
}
执行效率
  1. 最好情况时间复杂度：最好情况下，要排序的数据已经是有序的了，我们只需要进行一次冒泡操作，就可以结束了，所以最好情况时间复杂度是 O(n)。
  2. 最坏情况时间复杂度：最坏情况下，要排序的数据刚好是倒序排列的，我们需要进行 n 次冒泡操作，所以最坏情况时间复杂度为 O(n2)。
  3. 平均情况时间复杂度：平均情况下，需要 n * (n-1)/4 次交换操作，而比较操作肯定要比交换操作多，所以平均情况下的时间复杂度就是 O(n2)。
内存消耗
  1. 冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为 O(1)，是一个原地排序算法。
稳定性
  1. 在冒泡排序中，当两个值相等，可不做位置交换，故是稳定排序算法。

插入排序

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

代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int[] insertionSort(int[] arr) {

    for (int i = 1; i < arr.length; i++) {

        int temp = arr[i];
        int j = i - 1;
        // 查找插入位置
        for (; j >= 0; j--) {
            if (arr[j] > temp) {
            	// 数据搬移
                arr[j + 1] = arr[j];
            } else {
                break;
            }
        }

        arr[j + 1] = temp;
    }

    return arr;
}
执行效率
  1. 最好情况时间复杂度：最好情况下，要排序的数据已经是有序的了，每次只需要比较一个数据就能确定插入的位置，所以最好情况时间复杂度是 O(n)。
  2. 最坏情况时间复杂度：最坏情况下，要排序的数据刚好是倒序排列的，每次插入都相当于在数组的第一个位置插入新的数据，所以需要移动大量的数据，所以最坏情况时间复杂度为 O(n2)。
  3. 平均情况时间复杂度：每次插入操作都相当于在数组中插入一个数据，循环执行 n 次插入操作，所以平均情况下的时间复杂度就是 O(n2)。
内存消耗
  1. 插入排序算法的运行只需要常量级的临时空间，所以空间复杂度是 O(1)，是一个原地排序算法。
稳定性
  1. 在插入排序中，对于值相同的元素，我们可以选择将后面出现的元素，插入到前面出现元素的后面，故是稳定排序算法。

选择排序

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

代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int[] selectionSort(int[] arr) {

    for (int i = 0; i < arr.length; i++) {

        int minIndex = i;
        for (int j = arr.length - 1; j > i; j--) {

            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }

        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }

    return arr;

}
执行效率
  1. 选择排序中，无论数组数据是否有序，每个循环都必需完整执行。所以最好情况、最坏情况和平均情况的时间复杂度都为 O(n2)。
内存消耗
  1. 选择排序算法的运行只需要常量级的临时空间，所以空间复杂度是 O(1)，是一个原地排序算法。
稳定性
  1. 在选择排序中，选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性，故是不稳定排序算法。

归并排序

归并排序采用分治思想，将 n 个元素从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并，采用递归操作。这样整个数组就都有序了。

代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public static int[] mergeSort(int[] arr) {

    int[] result = new int[arr.length];
    mergeSortRecursive(arr, result, 0, arr.length - 1);

    return arr;
}

private static void mergeSortRecursive(int[] arr, int[] result, int start, int end) {
    if (start >= end) {
        return;
    }

    int len = end - start;
    int mid = (len >> 1) + start;
    int start1 = start;
    int end1 = mid;
    int start2 = mid + 1;
    int end2 = end;

    mergeSortRecursive(arr, result, start1, end1);
    mergeSortRecursive(arr, result, start2, end2);

    int k = start;
    while (start1 <= end1 && start2 <= end2) {
        result[k++] = arr[start1] <= arr[start2] ? arr[start1++] : arr[start2++];
    }

    while (start1 <= end1) {
        result[k++] = arr[start1++];
    }
    while (start2 <= end2) {
        result[k++] = arr[start2++];
    }

    int i = start;
    while (i <= end) {
        arr[i] = result[i];
        i++;
    }
}
执行效率
  1. 归并排序中，无论数组数据是否有序，每个操作都必需完整执行。所以最好情况、最坏情况和平均情况的时间复杂度都为 O(nlogn)。
内存消耗
  1. 归并排序需要一个大小和原数组相同的临时数组，所以归并排序的空间复杂度为 O(n)。
稳定性
  1. 归并排序中，对于前后两部分元素中含有相等的元素，只需将前半部分元素先放入到临时数组中，这样就保证了值相同的元素在合并前后的顺序保持不变，即归并排序为稳定排序法。

快速排序

快速排序也采用分治思想，从数列中挑出一个元素，称为 “基准”（pivot）。比基准值小元素的摆放在基准前面，比基准值大的元素摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public static int[] quickSort(int[] arr) {

    quickSortRecursive(arr, 0, arr.length - 1);

    return arr;

}

private static void quickSortRecursive(int[] arr, int start, int end) {

    if (start >= end) {
        return;
    }

    int left = start;
    int right = end - 1;

    while (left < right) {
        while (arr[left] <= arr[end] && left < right) {
            left++;
        }
        while (arr[right] >= arr[end] && left < right) {
            right--;
        }

        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }

    if (arr[left] > arr[end]) {
        int temp = arr[left];
        arr[left] = arr[end];
        arr[end] = temp;
    } else {
        left++;
    }

    quickSortRecursive(arr, start, left - 1);
    quickSortRecursive(arr, left + 1, end);

}
执行效率
  1. 最好情况时间复杂度：最好情况下，选择的 povit 都很合适。每次分区正好分成大小相等的两个小区间。此时最好情况时间复杂度是 O(nlogn)。
  2. 最坏情况时间复杂度：最坏情况下，如果原数组已经有序，每次选择的 povit 比较极端。需要进行大约 n 次分区操作。这种情况下时间复杂度就将为为 O(n2)。
  3. 平均情况时间复杂度：在大多数情况下时间复杂度为 O(nlogn)。
内存消耗
  1. 快速排序算法的运行只需要常量级的临时空间，所以空间复杂度是 O(1)，是一个原地排序算法。
稳定性
  1. 快速排序过程中，涉及到元素的交换，不能保证相等元素的顺序，所以快速排序为不稳定排序法。

二分查找

二分查找算法又叫折半查找算法。二分查找针对的是一个有序的数据集合，每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。

简单二分查找的代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static int bsearch(int[] arr, int value) {

    int low = 0;
    int high = arr.length - 1;

    while (low <= high) {
        int mid = low + ((high - low) >> 1);
        if (arr[mid] == value) {
            return mid;
        }
        if (arr[mid] > value) {
            high = mid - 1;
        }
        if (arr[mid] < value) {
            low = mid + 1;
        }
    }

    return -1;

}

执行效率

二分查找是一种非常高效的查找算法，它的时间复杂度为 O(logn).

二分查找的局限性

  1. 二分查找依赖的是顺序表结构，简单点说就是数组。因为它需要按照下标随机访问元素。
  2. 二分查找针对的是有序数据。
  3. 数据量太大不适合二分查找。因为二分查找底层需依赖数组，需要连续的内存空间。当数据量很大时，对内存的要求比较苛刻。