C_排序与查找

C_排序与查找

排序的前提是”比较”，排序的目的往往是”查找”。

排序

评估排序算法

时间复杂度

  • 最坏时间复杂度：在最不利的情况下，算法执行的时间。通常使用大O符号表示，如O(n²)、O(n log n)等。
  • 平均时间复杂度：算法在随机数据情况下的平均执行时间。通常作为衡量算法效率的主要指标。
  • 最好时间复杂度：在最理想情况下的执行时间，例如，当数组已排序时，算法的复杂度可能更低。

空间复杂度

  • 原地排序：算法是否需要额外的空间来完成排序，影响空间复杂度。
  • 辅助空间：需要额外的存储空间进行辅助处理。

稳定性

  • 稳定排序：两个元素相等，它们在排序后的顺序与排序前相同，称为稳定排序。

    稳定排序算法：冒泡排序、插入排序、归并排序、计数排序、基数排序。

    不稳定排序算法：选择排序、快速排序、堆排序。

排序算法

插入排序

直接插入排序

算法思想

构建有序序列。对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。（类似扑克牌）

具体步骤如下：

  • 从数组的第二个元素开始（第一个元素默认是有序的）。
  • 将当前元素与前面已经排好序的元素进行比较，找到适当的位置插入。
  • 重复以上步骤，直到整个数组有序。

插入排序

代码实现
1
2
3
4
5
6
7
8
9
10
11
qvoid insertionSort(int arr[], int n) {  
    for (int i = 1; i < n; i++) {		// 从数组的第二个元素开始处理
        int key = arr[i];  // 当前需要插入的元素
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {		// 将前面已经排好序的元素与key比较，找到插入位置
            arr[j + 1] = arr[j];  // 将大于key的元素向后移
            j--;
        }
        arr[j + 1] = key;  // 在找到的位置插入key
    }
}
算法分析

  1. 时间复杂度

    • 最优时间复杂度：**O(n)**。当输入数组已经有序时，只需要逐个扫描，每次比较一次即可。
    • 最坏时间复杂度：**O(n²)**：当输入数组是逆序排列时，每插入一个元素，都需要将已排序部分的所有元素向右移动，比较次数和移动次数都达到最大，时间复杂度为 O(n²) 。
    • 平均时间复杂度：**O(n²)**：在随机排列的数组中，插入排序的平均时间复杂度也是 O(n²) 。

  2. 空间复杂度：**O(1)**。插入排序只需要常量级的额外空间用于临时存储key变量。

  3. 稳定性：稳定。相等元素在排序过程中不会交换顺序。

折半排序

算法思想

折半排序算法是插入排序算法的一种改进。通常，插入排序在插入新元素时需要从头到尾进行线性搜索，找到适当的位置。而折半插入排序通过在已排序的序列中使用二分查找（也称折半查找）来确定插入位置，从而减少比较次数。

折半插入排序的基本步骤如下：

  • 排序过程与插入排序相似：依次将每个元素插入到前面已经排好序的子数组中。
  • 查找插入位置时使用二分查找法来代替逐一比较，从而减少查找的时间复杂度。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void binaryInsertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];  // 待插入的元素
        int left = 0, right = i - 1;   
        while (left <= right) {		// 二分查找插入位置
            int mid = left + (right - left) / 2;
            if (arr[mid] > key)
                right = mid - 1;
            else
                left = mid + 1;
        }        
        for (int j = i - 1; j >= left; j--) {		// 移动元素以腾出位置
            arr[j + 1] = arr[j];
        }       
        arr[left] = key;	 // 插入元素
    }
}
算法分析

  1. 时间复杂度

    • 最优时间复杂度：**O(n)**。当输入数组已经有序时，只需要找到正确位置而无需移动，查找时间为 O(logn)，但由于元素移动的过程仍然是线性的，所以最好的时间复杂度仍然是 O(n²)。虽然折半插入排序减少了比较次数，但由于元素插入时需要移动数据，其时间复杂度并没有降低太多。
    • 最坏时间复杂度：**O(n²)**：当输入数组是逆序排列时，需要每次都将新元素插入到最前面，此时查找的复杂度为 O(logn)，但移动元素的复杂度为 O(n)，最坏的时间复杂度仍然是 O(n²)。
    • 平均时间复杂度：**O(n²)**：查找和移动元素的综合开销不会大幅减少。

  2. 空间复杂度：**O(1)**。插入排序只需要常量级的额外空间用于临时存储key变量。

  3. 稳定性：稳定。相等元素在排序过程中不会交换顺序。

希尔排序

算法思想

希尔排序（Shell Sort）是插入排序的一种优化版本，旨在减少数据移动次数来提高排序效率。希尔排序通过引入“增量分组”的方式，对原数组进行分组，使每组内部进行插入排序。随着增量的不断缩小，分组越来越少，直到增量缩小为1时，整个数组变为有序。

希尔排序的关键是增量序列的选择，常用的增量序列是n/2, n/4, ..., 1，即每次将间隔减半。

希尔排序

代码实现
1
2
3
4
5
6
7
8
9
10
11
12
void shellSort(int arr[], int n) {
    for (int gap = n / 2; gap > 0; gap /= 2) {		// 初始间隔 gap 设为数组长度的一半，然后每次减半
        for (int i = gap; i < n; i++) {		// 从 gap 开始逐步对每个子序列进行插入排序
            int temp = arr[i];  // 保存当前元素
            int j;
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {//将 arr[i] 插入到子序列中
                arr[j] = arr[j - gap];  // 将较大的元素后移
            }
            arr[j] = temp;  // 将当前元素放入正确位置
        }
    }
}
算法分析
  1. 时间复杂度：希尔排序的时间复杂度与增量序列的选择有关。常见的增量序列为 n/2, n/4, …, 1。
    • 最优情况： **O(nlogn)**。实际运行中常显著优于插入排序。
    • 最坏情况： **O(n²)**。使用更优化的增量序列（如Hibbard增量序列）时，最坏时间复杂度可以降低到 O(n^3/2) 或更低。
    • 平均时间复杂度： **O(n^1.3)**，具体取决于增量序列的选择。
  2. 空间复杂度：O(1)。希尔排序是原地排序算法，不需要额外的存储空间。
  3. 稳定性：不稳定。相同元素在不同的增量分组时可能会被打乱其相对顺序。

交换排序

冒泡排序

算法思想

通过多次遍历待排序的数组，每一轮比较相邻的两个元素，将较大的元素逐步“冒泡”到数组的末尾。整个过程重复进行，直到所有元素按从小到大的顺序排列。

具体步骤如下：

  • 从第一个元素开始，比较相邻的两个元素。
  • 如果前一个元素比后一个大，则交换两者的位置。
  • 每一轮遍历后，最大元素会移动到数组末尾。
  • 重复上述步骤，直到所有元素有序。

冒泡排序

代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void bubbleSort(int arr[], int n) { 
    for (int i = 0; i < n - 1; i++) {		// 外层循环控制遍历的轮数       
        int swapped = 0;		// 标志变量，检测本轮是否有元素交换
        for (int j = 0; j < n - i - 1; j++) {		// 内层循环比较相邻元素并交换
            // 如果前一个元素比后一个大，则交换
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;     
                swapped = 1;		// 标记有元素发生交换
            }
        }
        if (swapped == 0) {		// 如果没有发生交换，说明数组已排序，提前结束
            break;
        }
    }
}
算法分析
  1. 时间复杂度：
    • 最优情况（已排序的数组）： **O(n)**。数组本身就是有序的，冒泡排序只需进行一轮比较，无需交换。
    • 最坏情况（逆序数组）： **O(n²)**。在数组完全逆序的情况下，算法需要进行 n-1 轮排序，每轮排序需要 n-1-i 次比较和交换
    • 平均时间复杂度： **O(n²)**。大部分排序情况都需要多轮比较和交换。在没有特殊信息的情况下，平均情况下冒泡排序的时间复杂度仍为O(n²)。
  2. 空间复杂度：O(1)。冒泡排序是原地排序算法，不需要额外的存储空间。
  3. 稳定性：稳定。相等元素在排序过程中不会交换顺序。

快速排序

算法思想

快速排序（Quicksort）是一种分治法排序算法。其基本思想是：

  1. 选择一个基准元素（Pivot），可以是数组的第一个元素、中间元素或随机选择。
  2. 将数组划分成两部分：
    • 左部分包含所有小于基准元素的数；
    • 右部分包含所有大于基准元素的数。
  3. 对左、右两部分递归地进行快速排序。
  4. 合并结果，即可得到一个有序数组。

关键步骤：

  • 分区（Partition）：每次根据基准元素将数组分为两部分。
  • 递归（Recursion）：对左右子数组分别进行快速排序。

快速排序

代码实现
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
// 快速排序的分区函数
int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // 选择最右边元素作为基准
    int i = low - 1;  // i 是小于 pivot 的元素的索引
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {  // 若当前元素小于基准
            i++;  // 增加小于 pivot 区域的索引
            // 交换 arr[i] 和 arr[j]
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    // 将基准元素放到正确的位置
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;  // 返回基准的最终位置
}

// 快速排序函数
void quickSort(int arr[], int low, int high) {
    if (low < high) {       
        int pi = partition(arr, low, high);		// 获取分区位置     
        quickSort(arr, low, pi - 1);		// 递归排序左半部分
        quickSort(arr, pi + 1, high);		// 递归排序右半部分
    }
}
算法分析
  1. 时间复杂度：
    • 最优情况： **O(nlogn)**。每次划分正好将数组一分为二。
    • 最坏情况： **O(n²)**。每次划分不平衡（如每次选择的基准恰好是数组的最大或最小值）
    • 平均时间复杂度： **O(nlogn)**。其中 n 是数组的元素个数，logn 是递归调用的层数。
  2. 空间复杂度：O(nlogn)。快速排序是原地排序算法，递归调用栈的深度为 logn。最坏情况下，递归深度为 O(n)，最坏空间复杂度为 **O(n)**。
  3. 稳定性：不稳定。在划分过程中，可能会交换相同元素的相对位置。

选择排序

简单选择排序

算法思想

在未排序的序列中找到最小（或最大）的元素，将其放到序列的起始位置。然后，继续在剩余未排序的序列中重复该操作，直到整个序列有序。

具体步骤如下：

​ 1. 从未排序的部分中选择最小的元素。

​ 2. 将该元素与未排序部分的第一个元素交换位置。

​ 3. 重复上述过程，直到所有元素排序完毕。

选择排序

代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void selectionSort(int arr[], int n) {
    int i, j, minIdx, temp;    
    for (i = 0; i < n - 1; i++) {		// 遍历数组中的每一个元素
        minIdx = i;		// 假设当前i位置的元素是未排序部分中的最小值   
        for (j = i + 1; j < n; j++) {		// 在未排序的部分中寻找最小值
            if (arr[j] < arr[minIdx]) {
                minIdx = j;  // 记录最小值的索引
            }
        }  
        if (minIdx != i) {		// 如果找到的最小值不是当前i位置的元素，则交换
            // 交换 arr[i] 和 arr[minIdx]
            temp = arr[i];
            arr[i] = arr[minIdx];
            arr[minIdx] = temp;
        }
    }
}
算法分析
  1. 时间复杂度：
    • 最优情况（已排序的数组）： **O(n²)**。选择排序每次都需要遍历未排序部分的元素 ，最好情况也需要执行 n 次选择操作，每次操作时间为 O(n-i) 次比较
    • 最坏情况（逆序数组）： **O(n²)**。无论数据原始顺序如何，算法都需要遍历每一个元素。
    • 平均时间复杂度： **O(n²)**。由于选择排序与输入的顺序无关，每次都要遍历未排序部分。
  2. 空间复杂度：O(nlogn)。选择排序是原地排序算法，只需要常量级的额外空间来存储临时变量（用于交换）。
  3. 稳定性：不稳定。选择排序在选择最小元素并交换时，可能会破坏原本的相对顺序。

堆排序

算法思想

堆排序是一种基于二叉堆的数据结构的排序算法。堆是一种特殊的完全二叉树，可以分为最大堆和最小堆。在最大堆中，父节点的值总是大于等于其子节点的值；在最小堆中，父节点的值总是小于等于其子节点的值。

堆排序的基本思想是：

​ 1. 构建最大堆：将无序数组调整为最大堆，使得堆顶元素（即根节点）为整个数组的最大值。

​ 2. 交换堆顶元素和末尾元素：将堆顶元素（最大值）与堆的最后一个元素交换，最大元素就位于数组的最后，并从堆中移除。

​ 3. 调整堆：对剩余的元素进行堆调整，重复上述步骤，直到所有元素有序。

代码实现
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
// 堆调整函数：调整以 i 为根节点的子树，使其满足最大堆的性质
// n 是数组的长度，i 是当前根节点的索引
void heapify(int arr[], int n, int i) {
    int largest = i;     // 初始化 largest 为根节点 i
    int left = 2 * i + 1; // 左子节点索引
    int right = 2 * i + 2; // 右子节点索引
    // 如果左子节点存在且大于根节点
    if (left < n && arr[left] > arr[largest])
        largest = left;
    // 如果右子节点存在且大于当前 largest
    if (right < n && arr[right] > arr[largest])
        largest = right;
    // 如果 largest 不是根节点
    if (largest != i) {
        // 交换根节点和最大值节点
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        // 递归调整子树
        heapify(arr, n, largest);
    }
}

// 堆排序函数：对数组 arr 进行堆排序
void heapSort(int arr[], int n) {
    // 构建最大堆
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
    // 逐步将堆顶元素（最大值）移动到数组末尾
    for (int i = n - 1; i >= 0; i--) {
        // 将堆顶元素与当前未排序部分的最后一个元素交换
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        // 调整剩余元素形成新的最大堆
        heapify(arr, i, 0);
    }
}
算法分析
  • 构建堆：构建最大堆的过程需要遍历所有非叶子节点，对每个节点进行堆调整。调整一个节点的时间复杂度为 O(logn)，总的构建堆时间复杂度为 O(n)。
  • 排序过程：在堆排序过程中，每次取出堆顶元素（最大值），然后对剩余的元素进行堆调整，整个排序过程需要进行 n-1 次堆调整，每次调整的时间复杂度为 O(logn)，总的排序时间复杂度为 O(nlogn)。

  1. 时间复杂度：

    • 最坏情况：O(nlogn)

    • 平均情况：O(nlogn)

    • 最好情况：O(nlogn)

  2. 空间复杂度：**O(1)**。 堆排序在排序过程中只需要常数级别的额外空间来进行交换操作和递归调用。

  3. 稳定性： 不稳定。在堆调整过程中，元素之间的相对顺序可能会被改变。当父节点和子节点交换时，原本相同的两个元素可能会被打乱顺序。

归并排序

算法思想

归并排序（Merge Sort）是一种分治算法。其核心思想是将待排序数组递归地分成两半，分别对左右两部分进行排序，最后将两部分合并成一个有序数组。

分治步骤：

 1.	**分**：将数组递归地分成两半，直到每个子数组只包含一个元素（此时认为子数组是有序的）。
 2.	**治**：将两个有序的子数组合并成一个有序数组。
 3.	**合并**：将小问题合并成大问题，最终将整个数组合并为一个有序数组。

归并排序的核心步骤是合并两个有序数组，过程是线性时间的。

归并排序

代码实现

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
43
44
45
46
47
48
// 归并函数，将两个有序的子数组合并为一个有序数组
void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;  // 左边子数组的大小
    int n2 = right - mid;     // 右边子数组的大小
    // 创建临时数组存储左右两部分
    int L[n1], R[n2];
    // 将数据复制到临时数组
    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int i = 0; i < n2; i++)
        R[i] = arr[mid + 1 + i];
    // 合并两个临时数组
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {  // 保证稳定性：左边元素 <= 右边元素
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    // 如果左边还有剩余元素，直接复制
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    // 如果右边还有剩余元素，直接复制
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// 归并排序的递归函数
void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;  // 计算中间点
        // 递归地对左右两部分进行排序
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        // 合并已排好序的两部分
        merge(arr, left, mid, right);
    }
}

算法分析

  • 归并排序在最优、最坏和平均情况下的时间复杂度都是 **O(nlog n)**。其中 n 是数组的长度，logn 是由于递归分割数组的过程，n 是合并两个有序子数组的时间。

    时间复杂度分析：

    • 归并排序的每一次分解步骤，都会将数组对半划分，整个过程为 O(log n) 次。
    • 在每次划分后的合并步骤中，需要花费 O(n) 的时间来合并两个有序子数组。
    • 总时间复杂度为 O(nlogn)。

  1. 时间复杂度：

    • 最坏情况：O(nlogn)

    • 平均情况：O(nlogn)

    • 最好情况：O(nlogn)

  2. 空间复杂度：**O(n)**。归并排序的空间复杂度主要来自递归调用栈以及临时数组。每次递归调用会使用 O(logn) 的栈空间，而临时数组则需要 O(n) 的额外空间来存储子数组。

  3. 稳定性：稳定。排序时相等元素的相对位置不会改变。若两个元素相等，会优先将左边的元素放入结果数组。

基数排序

算法思想

基数排序是一种非比较排序算法，基于“位”的思想来排序。它适合用于对整数或字符串等结构较为固定的对象进行排序。该算法的核心思想是将数据拆分成多个部分（如个位、十位、百位等），逐步对每一部分进行排序，最终得到有序的数据序列。基数排序有两种方式：

  • LSD（Least Significant Digit）：从最低位开始排序（常用于排序数字）。

  • MSD（Most Significant Digit）：从最高位开始排序（常用于排序字符串等）。

主要步骤如下：

  1. 将数据按位（从最低位到最高位）进行分配。找出待排序数组中最大元素的位数。
  2. 从最低位开始，对数组元素按位排序，使用稳定的排序算法（如计数排序或桶排序）对各个位上的数进行排序。
  3. 重复步骤2，直到最高位也排序完毕。

基数排序的特点是，每一位上的排序必须是稳定的，才能保证排序的正确性。

代码实现

假设整数的范围是0到999，并且使用计数排序作为每一位的排序方法。主要包含核心的radixSort和辅助的计数排序countSort函数。

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
43
// 获取数组中的最大值
int getMax(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    return max;
}
// 按照当前位数进行计数排序，exp 是对应的位数（1表示个位，10表示十位，依次类推）
void countingSort(int arr[], int n, int exp) {
    int output[n];  // 输出数组
    int count[10] = {0};  // 计数数组，用来存储每个桶中的元素个数
    // 计算当前位数的出现次数
    for (int i = 0; i < n; i++) {
        int digit = (arr[i] / exp) % 10;
        count[digit]++;
    }
    // 修改计数数组，使其包含当前位数的正确位置
    for (int i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }
    // 从后向前遍历数组，确保计数排序是稳定的
    for (int i = n - 1; i >= 0; i--) {
        int digit = (arr[i] / exp) % 10;
        output[count[digit] - 1] = arr[i];
        count[digit]--;
    }
    // 将排序结果复制回原数组
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}
// 基数排序主函数
void radixSort(int arr[], int n) {
    // 找到数组中的最大数，以确定最大位数
    int max = getMax(arr, n);
    // 从个位开始，逐位对数组进行排序
    for (int exp = 1; max / exp > 0; exp *= 10) {
        countingSort(arr, n, exp);
    }
}

算法分析

设数组中元素的最大值为M，数组的长度为n。最大值M的位数为d，每一位使用计数排序，其复杂度为O(n + k)，其中k为计数排序的范围（对10个数字的计数排序，k=10）。总时间复杂度为 O(d*(n + k)) ，当k为常数时，复杂度为 O(d*n) 。

  • 对于整数来说，d通常较小，可以认为d为常数，基数排序的时间复杂度为**O(n)**。
  • 元素范围较大，例如需要排序非常大的数字， d 会增大，算法的时间复杂度也会相应提高。

  1. 时间复杂度：

    • 最坏情况：O(n)

    • 平均情况：O(n)

    • 最好情况：O(n)

  2. 空间复杂度：**O(n+k)**。其中 n 是待排序元素的个数，k 是计数排序的桶数量。在本算法中，计数排序的桶数量是 10（对应十进制数的个位、十位、百位等），即线性空间复杂度。

  3. 稳定性：稳定。特别是在每一位的排序中使用稳定的排序算法（如计数排序）时，可以保证两个相同元素在排序前后的相对顺序不变。

查找

评估查找算法

时间复杂度

  • 最坏情况时间复杂度：算法在最坏情况下的运行时间。例如，线性查找在最坏情况下需要 O(n)，而二分查找的最坏情况是 O(log n)。
  • 平均情况时间复杂度：评估算法在不同输入条件下的平均表现。平均情况下的算法性能。例如，哈希查找在没有冲突时，平均复杂度为 O(1)，而在发生冲突时复杂度升高。
  • 最优情况时间复杂度：算法在最理想的情况下的性能。例如，在二分查找中，若目标元素恰好是数组的中间值，查找时间为 O(1)。

空间复杂度

  • 额外空间需求：是否需要额外空间进行数据存储或处理。例如，线性查找不需要额外空间，复杂度为 O(1)，而哈希查找需要额外的空间来存储哈希表。
  • 辅助数据结构：某些查找算法依赖额外的数据结构，比如跳表或哈希表，需要额外的内存空间来存储索引或哈希值。

前提条件

  • 有序数据：算法是否需要数据有序，如二分查找，要求数据必须是已排序的。
  • 数据结构：不同查找算法适用于不同的数据结构。例如，哈希查找适用于哈希表，二分查找适用于有序数组，广度优先搜索（BFS）适用于图。
  • 动态数据集：某些查找算法更适合处理动态数据集，如跳表和哈希查找，而二分查找适用于静态有序数组。

鲁棒性

  • 最坏情况表现：算法在最坏情况下的效率。例如，哈希查找在最坏情况下退化到 O(n)（当哈希冲突严重时），而二分查找始终保持 O(log n)。
  • 容错能力：查找算法是否对异常输入（如空数组、数据不匹配）做了合理处理，防止崩溃或出错。
  • 抗数据分布能力：部分查找算法对数据分布较为敏感，如插值查找对均匀分布数据表现好，但对于不均匀分布的数据，性能下降明显。

稳定性

  • 动态数据处理能力：某些查找算法需要在数据动态变化时仍保持高效。例如，跳表在数据插入、删除时能保持较好的查找性能，时间复杂度是 O(log n)。
  • 重复元素的处理：查找算法是否能正确处理重复元素，如线性查找可以找到多个匹配项，但二分查找需要特殊处理以找到第一个或最后一个匹配元素。

线性查找

算法思想

线性查找（Linear Search）核心思想是：从数组的第一个元素开始，依次检查每个元素，直到找到目标元素或数组末尾为止。线性查找适用于无序数组，不需要对数组进行排序。

代码实现

1
2
3
4
5
6
7
8
9
10
11
int linear_search(int arr[], int size, int target) {
    // 遍历数组中的每一个元素
    for (int i = 0; i < size; i++) {
        // 如果找到了目标值，返回其索引
        if (arr[i] == target) {
            return i;
        }
    }
    // 如果未找到目标值，返回 -1
    return -1;
}

算法分析

  1. 时间复杂度：

    • **最坏情况：O(n)**。在最坏的情况下（即目标元素在数组的末尾或者不存在），需要检查数组中的每一个元素。
    • **最好情况：O(1)**。在最好的情况下（即目标元素是数组的第一个元素），只需要一次比较。
    • **平均情况：O(n)**。目标元素可能在数组的任何位置，平均需要遍历数组的一半，即 n/2 次操作，时间复杂度仍然为 O(n)。

  2. 空间复杂度：**O(1)**。该算法只使用了一个额外的整型变量（用于循环计数），空间复杂度与输入数据的大小无关。

  3. 前提条件：无序数组。线性查找不要求数组有序，适合在任何情况下使用。

  4. 鲁棒性：鲁棒性强。算法本身不会对数组的内容做任何假设。即使数组中包含重复值、负数、零等，线性查找仍然可以正常工作。

  5. 稳定性：稳定。特别是在每一位的排序中使用稳定的排序算法（如计数排序）时，可以保证两个相同元素在排序前后的相对顺序不变。

二分查找

算法思想

二分查找（Binary Search）是一种在有序数组中查找目标值的高效算法。基本思想是：

  • 每次将查找范围缩小一半。
  • 假设有一个有序数组，并想在其中查找一个特定元素。首先比较目标值与中间元素的大小：
    • 如果目标值等于中间元素，直接返回该元素的索引。
    • 如果目标值小于中间元素，则只需继续在左半部分查找。
    • 如果目标值大于中间元素，则只需继续在右半部分查找。

不断重复，直到找到目标值，或者查找范围缩小为空，表明目标值不存在。

代码实现

  1. 循环实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int binarySearch(int arr[], int left, int right, int target) {
		while (left <= right) {    
        int mid = left + (right - left) / 2; 		// 计算中间索引 
        if (arr[mid] == target) {		// 如果目标值等于中间元素，返回索引
            return mid;
        }
        else if (arr[mid] > target) {		// 如果目标值小于中间元素，继续在左半部分查找
            right = mid - 1;
        }  
        else {		// 如果目标值大于中间元素，继续在右半部分查找
            left = mid + 1;
        }
    }
    // 未找到目标值，返回-1
    return -1;
}
  1. 递归实现
1
2
3
4
5
6
7
8
9
10
11
int bsearch(int arr[], int left, int right, int key) {
		if (left > right) return -1;
		// 递归公式
		int mid = left + (right - left >> 1);
		if (key < arr[mid]) return bsearch(arr, left, mid - 1, key);
		if (key > arr[mid]) return bsearch(arr, mid + 1, right, key);
		return mid;
}
int binary_search(int arr[], int n, int key) {
		return bsearch(arr, 0, n - 1, key);
}

算法分析

  1. 时间复杂度：

    • **最坏情况：O(logn)**。每次查找都会将范围缩小一半，需要进行的比较次数为 log₂n 次，时间复杂度为 O(logn)。
    • **最好情况：O(1)**。当目标值正好位于数组的中间位置时，只需进行一次比较即可找到目标值，此时复杂度为 O(1)。
    • **平均情况：O(logn)**。与最坏情况相同，平均情况下复杂度为 O(logn)。

  2. 空间复杂度：**O(1)**。由于只使用了常数级别的额外变量（如 left、right、mid）。

  3. 前提条件：

    • 数组有序：二分查找的前提是数组必须是有序的，若数组无序，算法无法正常工作。

    • 静态数组：二分查找适合用于静态数组，即数组元素在查找过程中不会改变。元素发生改变，需要先重新排序。

  4. 鲁棒性：

    • 目标值不存在的情况：目标值不在数组中，算法最终会将查找范围缩小至无效的区间（left > right），此时返回 -1，表示未找到目标值。

    • 数组为空：在调用函数时，数组为空（right < left），算法会直接返回 -1。

  5. 稳定性：不稳定。无法保证对于重复出现的元素总是返回第一个出现的索引。

跳表

算法思想

跳表（Skip List）是一种基于链表的数据结构。其核心思想是是在链表上建立多层“跳跃”索引，每层索引中的元素是下层链表的子集，索引层数越高包含的元素越少。

跳表特点：

  1. 跳表的结构是多级链表，最低层是原始链表，上面的每一层是索引链表；
  2. 查找、插入和删除操作依赖于索引，通过逐层查找可以减少比较次数，进而提高效率；
  3. 跳表的随机层数决定了效率，可以通过随机函数控制索引的生成。

代码实现

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// 定义跳表的最大层数
#define MAX_LEVEL 16
#define P 0.5  // 跳表中元素晋升的概率

// 跳表节点定义
typedef struct SkipListNode {
    int value;
    struct SkipListNode *forward[];  // 指向各层的前进指针数组
} SkipListNode;

// 跳表定义
typedef struct SkipList {
    int level;                      // 当前跳表的最大层数
    SkipListNode *header;           // 跳表的头节点
} SkipList;

// 创建节点
SkipListNode *createNode(int level, int value) {
    SkipListNode *node = (SkipListNode *)malloc(sizeof(SkipListNode) + level * sizeof(SkipListNode *));
    node->value = value;
    return node;
}

// 创建跳表
SkipList *createSkipList() {
    SkipList *list = (SkipList *)malloc(sizeof(SkipList));
    list->level = 0;  // 初始时，跳表层数为 0
    list->header = createNode(MAX_LEVEL, 0);  // 创建头节点
    for (int i = 0; i < MAX_LEVEL; i++) {
        list->header->forward[i] = NULL;
    }
    return list;
}

// 生成随机层数
int randomLevel() {
    int level = 1;
    while (((double)rand() / RAND_MAX) < P && level < MAX_LEVEL) {
        level++;
    }
    return level;
}

// 查找操作
SkipListNode *search(SkipList *list, int value) {
    SkipListNode *x = list->header;
    // 从最高层往低层查找
    for (int i = list->level - 1; i >= 0; i--) {
        while (x->forward[i] && x->forward[i]->value < value) {
            x = x->forward[i];
        }
    }
    x = x->forward[0];  // 到达底层后，前进到下一个节点
    if (x && x->value == value) {
        return x;  // 找到目标节点
    }
    return NULL;  // 未找到
}

// 插入操作
void insert(SkipList *list, int value) {
    SkipListNode *update[MAX_LEVEL];  // 记录更新路径
    SkipListNode *x = list->header;
    // 从最高层往低层查找插入位置
    for (int i = list->level - 1; i >= 0; i--) {
        while (x->forward[i] && x->forward[i]->value < value) {
            x = x->forward[i];
        }
        update[i] = x;  // 记录每一层的最后节点
    }
    
    int level = randomLevel();  // 生成该节点的随机层数
    if (level > list->level) {
        for (int i = list->level; i < level; i++) {
            update[i] = list->header;  // 新层初始化
        }
        list->level = level;  // 更新跳表的层数
    }

    // 创建新节点并插入
    x = createNode(level, value);
    for (int i = 0; i < level; i++) {
        x->forward[i] = update[i]->forward[i];
        update[i]->forward[i] = x;
    }
}

// 删除操作
void delete(SkipList *list, int value) {
    SkipListNode *update[MAX_LEVEL];
    SkipListNode *x = list->header;
    // 从最高层往低层查找删除位置
    for (int i = list->level - 1; i >= 0; i--) {
        while (x->forward[i] && x->forward[i]->value < value) {
            x = x->forward[i];
        }
        update[i] = x;
    }

    x = x->forward[0];  // 到达底层
    if (x && x->value == value) {
        // 更新每一层的前进指针，删除节点
        for (int i = 0; i < list->level; i++) {
            if (update[i]->forward[i] != x) break;
            update[i]->forward[i] = x->forward[i];
        }
        free(x);

        // 检查并更新跳表的层数
        while (list->level > 0 && list->header->forward[list->level - 1] == NULL) {
            list->level--;
        }
    }
}

算法分析

  1. 时间复杂度：

    • 查找操作：跳表的查找过程是从上层逐级往下查找，每一层的节点数期望是上一层的一半。查找的平均时间复杂度为 **O(log n)**，最坏情况下退化为 **O(n)**（所有元素都在最低层）。
    • 插入操作：插入操作需要找到插入位置，然后插入新节点。和查找过程类似，平均时间复杂度为 **O(log n)**。
    • 删除操作：删除操作与查找过程相似，找到要删除的节点，修改前驱节点的指针。平均时间复杂度为 **O(log n)**。

  2. 空间复杂度：**O(n)**。跳表需要为每个节点维护多层索引，索引的层数是随机生成的。平均情况下，跳表每一层的节点数量是前一层的 1/2。

  3. 前提条件：

    • 跳表是一种有序的数据结构，节点的值必须具有可比较性（例如整数、浮点数、字符串等可排序类型）。
    • 跳表在设计上依赖于随机层数的生成，随机数生成器需要良好表现，不能总是生成过大的层数或过小的层数。

  4. 鲁棒性：

    • 跳表的插入和删除操作依赖于随机层数生成，跳表的性能在实际运行时会有一定波动。虽然最坏情况下跳表的时间复杂度为 **O(n)**，但平均情况较好，能保持 **O(log n)**。
    • 跳表的鲁棒性体现在它可以通过随机层数来避免复杂的平衡操作，不像红黑树等需要严格的平衡调整。

  5. 稳定性：

    • 查找的稳定性：跳表的查找操作是确定的，即使数据随机插入，只要结构不发生变化，多次查找同一个值的结果一致，因此跳表的查找操作是稳定的。

    • 插入/删除的稳定性：由于跳表中的元素插入是基于随机层数生成的，插入和删除的效率会有所波动，但总体是稳定的。

哈希查找

算法思想

哈希查找（Hashing）是一种通过键值（Key）来直接访问数据的方法，其核心思想是将元素的存储位置和键值通过一个哈希函数关联起来，将关键字映射到数组中的一个位置，然后通过数组的下标直接找到对应的值。

  • 哈希函数（Hash Function）：负责将键值转换为数组索引。一个好的哈希函数应具有均匀性和简单性，避免大量冲突。
  • 哈希表（Hash Table）：利用数组实现的，存储元素的位置通过哈希函数计算得出。
  • 冲突处理：当两个不同的键值通过哈希函数得到相同的数组索引时，称为“冲突”。常用的冲突解决方法有开放地址法和链地址法。

代码实现

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
43
44
// 哈希表的最大容量
#define TABLE_SIZE 100
// 定义哈希表
int hashTable[TABLE_SIZE];
// 初始化哈希表，所有位置设置为-1表示空
void initHashTable() {
    for (int i = 0; i < TABLE_SIZE; i++) {
        hashTable[i] = -1;
    }
}
// 简单的哈希函数，将键值转换为数组索引
int hashFunction(int key) {
    return key % TABLE_SIZE;
}
// 插入键值
void insert(int key) {
    int index = hashFunction(key);  // 计算哈希值

    // 线性探测，处理冲突
    while (hashTable[index] != -1) {
        index = (index + 1) % TABLE_SIZE;  // 向后探测下一个位置
    }
    hashTable[index] = key;  // 插入键值
}
// 查找键值
int search(int key) {
    int index = hashFunction(key);  // 计算哈希值

    // 线性探测查找，处理冲突
    while (hashTable[index] != -1) {
        if (hashTable[index] == key) {
            return index;  // 找到键值，返回位置
        }
        index = (index + 1) % TABLE_SIZE;  // 向后探测下一个位置
    }
    return -1;  // 未找到，返回-1
}
// 删除键值
void delete(int key) {
    int index = search(key);  // 查找键值所在位置
    if (index != -1) {
        hashTable[index] = -1;  // 将对应位置设为空
    }
}

算法分析

  1. 时间复杂度：

    • **最坏情况：O(n)**。当发生大量冲突时，最坏情况下时间复杂度为 O(n) ，例如所有键值都映射到相同位置时，需要线性探测整个数组。
    • **最好情况：O(1)**。理想情况下，通过哈希函数能直接定位。
    • **平均情况：O(1)**。插入、查找和删除的平均时间复杂度为 O(1) ，理想情况下，通过哈希函数能直接定位。

  2. 空间复杂度：**O(n)**。哈希表的空间复杂度为 O(n)，其中 n 是哈希表的大小。

  3. 前提条件：

    • 哈希函数应设计合理，尽量均匀分布键值，避免产生大量冲突。

    • 表的大小应适当，通常选择一个比实际存储量略大的素数以减少冲突。

  4. 鲁棒性：

    • 目标值不存在的情况：对于不存在的元素，查找函数能返回 -1，表示未找到，具有良好的鲁棒性。

    • 插入函数能自动处理冲突，避免覆盖已有数据。

  5. 稳定性：不稳定。元素的插入和查找顺序不依赖于元素的原始顺序。

深度优先搜索

算法思想

深度优先搜索（Depth First Search, DFS）是一种遍历或搜索图或树数据结构的算法。其基本思想是沿着一个分支不断向前深入，直到找到目标或到达叶子节点。每当到达一个节点时，如果该节点的所有相邻节点都已经访问过或不可达，算法会回溯到上一个节点继续搜索未访问的相邻节点，直到所有节点都被访问。

DFS使用的是“栈”的思想（可以通过递归或显式使用栈结构来实现），即先探到最深处，然后逐步回溯。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#define MAX_NODES 100

// 图的邻接矩阵表示
int graph[MAX_NODES][MAX_NODES]; // 图的邻接矩阵
int visited[MAX_NODES]; // 标记节点是否已访问

// 深度优先搜索算法实现
void DFS(int node, int num_nodes) {
    visited[node] = 1; // 标记当前节点为已访问

    // 遍历所有相邻节点
    for (int i = 0; i < num_nodes; i++) {
        // 如果有相邻节点且未访问，继续深入
        if (graph[node][i] == 1 && !visited[i]) {
            DFS(i, num_nodes); // 递归调用
        }
    }
}

  • graph 是图的邻接矩阵，graph[i][j] = 1 表示节点 i 与节点 j 相连。

  • visited[i] 用于标记节点是否已经被访问，以避免重复遍历。

  • DFS 函数中，通过递归实现了从某个节点开始的深度优先搜索。

算法分析

  1. 时间复杂度：DFS的时间复杂度取决于图的表示方式，总的来说，DFS对稀疏图（边较少）和稠密图（边较多）都具有良好的性能表现。

    • 邻接矩阵： O(V^2) ，其中 V 是图中节点数。
    • 邻接表： O(V+E) ，其中 E 是图中边的数量。

  2. 空间复杂度：空间复杂度主要由递归栈占用

    • 邻接矩阵： O(V) ，其中 V 是图中节点数。
    • 邻接表： O(V^2) ，其中 V 是图中节点数。

  3. 前提条件：

    • 图可以是连通或非连通图。
    • 适用于无向图和有向图。
    • 对于递归实现，要求系统栈空间足够大，适合节点数量较小的图。如果图的节点非常多，递归深度过大可能会导致栈溢出，建议改用非递归方式（例如使用栈模拟递归）。

  4. 鲁棒性：

    • 需要考虑边界情况，例如图为空（没有节点或边）、只有一个节点、图不连通等特殊情况。
    • 需要处理节点数组越界、空指针等异常。

  5. 稳定性：不稳定。不同的执行顺序可能会导致不同的遍历路径，取决于邻接节点的访问顺序。

广度优先搜索

算法思想

广度优先搜索（Breadth First Search, BFS）是一种图遍历算法，通常用于无权图最短路径问题、连通分量搜索等问题。其基本思想是：从起始节点开始，先访问所有相邻节点，然后再逐层向外扩展，直到目标节点被访问或所有节点都被遍历完。

BFS 使用队列（Queue）来维护当前层级的节点，并确保节点按层级顺序访问。每次从队列中取出一个节点，访问其所有未访问的邻节点，将它们加入队列。

代码实现

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

#define MAX_VERTICES 100

// 队列结构
typedef struct {
    int items[MAX_VERTICES];
    int front;
    int rear;
} Queue;

// 初始化队列
void initQueue(Queue* q) {
    q->front = -1;
    q->rear = -1;
}

// 判断队列是否为空
bool isEmpty(Queue* q) {
    return q->front == -1;
}

// 入队
void enqueue(Queue* q, int value) {
    if (q->rear == MAX_VERTICES - 1) {
        return;  // 队列满了
    } else {
        if (q->front == -1) {
            q->front = 0;
        }
        q->rear++;
        q->items[q->rear] = value;
    }
}

// 出队
int dequeue(Queue* q) {
    int item;
    if (isEmpty(q)) {
        return -1;  // 队列为空
    } else {
        item = q->items[q->front];
        q->front++;
        if (q->front > q->rear) {
            q->front = q->rear = -1;
        }
        return item;
    }
}

// 广度优先搜索算法
void BFS(int graph[MAX_VERTICES][MAX_VERTICES], int startVertex, int numVertices) {
    Queue q;
    initQueue(&q);

    bool visited[MAX_VERTICES] = {false};  // 标记每个节点是否访问过
    visited[startVertex] = true;
    enqueue(&q, startVertex);

    while (!isEmpty(&q)) {
        int currentVertex = dequeue(&q);
        printf("访问节点 %d\n", currentVertex);

        // 遍历当前节点的所有邻接节点
        for (int i = 0; i < numVertices; i++) {
            if (graph[currentVertex][i] == 1 && !visited[i]) {
                visited[i] = true;  // 标记为已访问
                enqueue(&q, i);  // 将邻接节点加入队列
            }
        }
    }
}

算法分析

  1. 时间复杂度： O(V + E)，其中，V 是顶点的数量，E 是边的数量。在最坏情况下，BFS 需要遍历每个顶点和与其相连的每条边。

  2. 空间复杂度：存储图的邻接矩阵和队列。

    • 队列：最多存储所有顶点，即 O(V)。
    • 访问标记数组：存储每个顶点的访问状态，也是 O(V)。

  3. 前提条件：

    • 图的存储方式：本实现使用邻接矩阵表示图，因此适用于稠密图。如果图是稀疏的，可以改用邻接表来优化空间复杂度。
    • 输入合法性：输入的图应是连通图（探索全图），并且顶点的索引应合法。

  4. 鲁棒性：

    • 队列溢出检测：本代码中检查了队列是否满，但没有处理队列溢出的错误处理机制（如扩展队列容量）。对于大图来说，需要更鲁棒的动态队列实现。

      图遍历的边界处理：该算法可以处理连通图和非连通图，但要确保输入的顶点索引在有效范围内（即 [0, numVertices-1] 之间）。

  5. 稳定性：稳定。按照层级顺序依次访问每个顶点，保证在最短路径问题中，较早访问的顶点优先处理，不会跳跃式访问。