（C++数据结构）查找算法与排序算法详解

目录

1. 有序向量的查找算法
2. 排序算法
3. 算法复杂度分析

---

1. 有序向量的查找算法

1.1 二分查找（Binary Search）

二分查找是最基本的有序向量查找算法，时间复杂度为O(log n)。

基本实现

int binarySearch(int A[], int lo, int hi, int e) {
    while (lo < hi) {
        mi = (lo + hi) >> 1;  // 中间位置，右移1位相当于除以2
        if (e < A[mi]) hi = mi;           // 目标在左半区间
        else if (e > A[mi]) lo = mi + 1;  // 目标在右半区间
        else return mi;                   // 找到目标
    }
    return -1;  // 未找到
}

改进版本

int binarySearchImproved(int A[], int lo, int hi, int e) {
    while (lo < hi) {
        mi = (lo + hi) >> 1;
        if (e < A[mi]) hi = mi;
        else lo = mi + 1;  // 右子区间不包含mi
    }
    return --lo;  // 返回不大于e的最大元素位置
}

关键点：

• 循环条件 lo < hi 确保区间有效
• mi = (lo + hi) >> 1 避免溢出
• 平均查找长度为 O(1.5 log n)

1.2 插值查找（Interpolation Search）

插值查找适用于均匀分布的有序向量，通过线性插值预测目标位置。

核心公式

$$\frac{mi-lo}{hi-lo}=\frac{e-A[lo]}{A[hi]-A[lo]}$$
解得：
$$mi=lo+(hi-lo)\cdot \frac{e-A[lo]}{A[hi]-A[lo]}$$

实现代码

int interpolationSearch(int A[], int lo, int hi, int e) {
    while (lo <= hi && e >= A[lo] && e <= A[hi]) {
        if (lo == hi) {
            if (A[lo] == e) return lo;
            return -1;
        }
        
        // 插值公式计算预测位置
        mi = lo + ((double)(hi - lo) / (A[hi] - A[lo])) * (e - A[lo]);
        
        if (A[mi] == e) return mi;
        if (A[mi] < e) lo = mi + 1;
        else hi = mi - 1;
    }
    return -1;
}

示例分析

对于数组 V = {2,3,5,7,11,13,17,19,23}，查找元素 e=7：
$$\frac{mi-0}{8-0}=\frac{7-2}{23-2}=\frac{5}{21}$$
$$mi=8\times \frac{5}{21}\approx 1.9\to mi=1$$
复杂度分析：

• 平均时间复杂度：O(log log n)
• 最坏时间复杂度：O(n)

1.3 斐波那契查找（Fibonacci Search）

斐波那契查找利用斐波那契数列的特性进行分割，接近黄金比例分割。

斐波那契数列

k:  0  1  2  3  4  5  6   7
fib:0  1  1  2  3  5  8  13

核心思想

• 数组长度满足：n = fib(k) - 1
• 中间位置：mi = fib(k-1) - 1
• 左子区间长度：fib(k-2) - 1
• 右子区间长度：fib(k-1) - 1

实现代码

int fibonacciSearch(int A[], int n, int e) {
    // 初始化斐波那契数列
    int fib[20];
    fib[0] = 0; fib[1] = 1;
    for (int i = 2; i < 20; i++) {
        fib[i] = fib[i-1] + fib[i-2];
    }
    
    // 找到最小的k使得fib(k) - 1 >= n
    int k = 0;
    while (fib[k] - 1 < n) k++;
    
    int lo = 0, hi = n - 1;
    
    while (lo <= hi) {
        mi = lo + fib[k-1] - 1;
        
        if (mi > hi) {  // 处理边界情况
            mi = hi;
        }
        
        if (A[mi] == e) return mi;
        if (A[mi] < e) {
            lo = mi + 1;
            k = k - 2;  // 右子区间
        } else {
            hi = mi - 1;
            k = k - 1;  // 左子区间
        }
    }
    return -1;
}

示例分析

对于数组 V = {1,2,3,4,5,6,7}，查找元素 e=1：

1. n=7, fib(6)-1=7, k=6
2. mi = fib(5)-1 = 4, V[4]=5 > 1, hi=3, k=5
3. mi = fib(4)-1 = 2, V[2]=3 > 1, hi=1, k=4
4. mi = fib(3)-1 = 1, V[1]=2 > 1, hi=0, k=3
5. mi = fib(2)-1 = 0, V[0]=1, 找到目标
   访问序列：[5,3,2,1]

---

2. 排序算法

2.1 冒泡排序及改进

基本冒泡排序

void bubbleSort(int A[], int n) {
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-i-1; j++) {
            if (A[j] > A[j+1]) {
                swap(A[j], A[j+1]);
            }
        }
    }
}

改进版本（记录最后交换位置）

int bubble(int A[], int lo, int hi) {
    Rank last = lo;
    while (++lo < hi) {
        if (A[lo-1] > A[lo]) {
            swap(A[lo-1], A[lo]);
            last = lo;  // 记录最后交换位置
        }
    }
    return last;
}
void improvedBubbleSort(int A[], int n) {
    int lo = 0, hi = n;
    while (lo < (hi = bubble(A, lo, hi)));
}

改进原理：记录每次循环中最后一次交换的位置，下一轮只需比较到该位置即可。

2.2 归并排序（Merge Sort）

归并排序采用分治策略，时间复杂度O(n log n)，是稳定排序。

核心合并算法

void merge(int A[], int lo, int mid, int hi) {
    int* B = new int[hi-lo+1];  // 临时数组
    int i = lo, j = mid+1, k = 0;
    
    // 合并两个有序子数组
    while (i <= mid && j <= hi) {
        if (A[i] <= A[j]) B[k++] = A[i++];
        else B[k++] = A[j++];
    }
    
    // 复制剩余元素
    while (i <= mid) B[k++] = A[i++];
    while (j <= hi) B[k++] = A[j++];
    
    // 复制回原数组
    for (int t = 0; t < k; t++) {
        A[lo+t] = B[t];
    }
    
    delete[] B;
}
void mergeSort(int A[], int lo, int hi) {
    if (hi - lo < 2) return;  // 递归基
    
    int mid = (lo + hi) >> 1;
    mergeSort(A, lo, mid);    // 排序左半部分
    mergeSort(A, mid, hi);    // 排序右半部分
    merge(A, lo, mid, hi);    // 合并
}

2.3 基数排序（Radix Sort）

基数排序按位数从低到高进行排序，要求每位排序时保持稳定性。

实现代码

// 获取数字的第d位数字
int getDigit(int num, int d) {
    while (d-- > 1) {
        num /= 10;
    }
    return num % 10;
}
// 对数组的第d位进行计数排序
void countingSortByDigit(int A[], int n, int d) {
    const int RADIX = 10;
    int* B = new int[n];
    int count[RADIX] = {0};
    
    // 统计各数字出现次数
    for (int i = 0; i < n; i++) {
        count[getDigit(A[i], d)]++;
    }
    
    // 计算累积位置
    for (int i = 1; i < RADIX; i++) {
        count[i] += count[i-1];
    }
    
    // 从右向左填充，保证稳定性
    for (int i = n-1; i >= 0; i--) {
        int digit = getDigit(A[i], d);
        B[count[digit]-1] = A[i];
        count[digit]--;
    }
    
    // 复制回原数组
    for (int i = 0; i < n; i++) {
        A[i] = B[i];
    }
    
    delete[] B;
}
void radixSort(int A[], int n) {
    if (n <= 1) return;
    
    // 找到最大值，确定位数
    int maxVal = A[0];
    for (int i = 1; i < n; i++) {
        if (A[i] > maxVal) maxVal = A[i];
    }
    
    // 按位数从低到高排序
    for (int d = 1; maxVal / d > 0; d *= 10) {
        countingSortByDigit(A, n, d);
    }
}

示例演示

对数组 [170, 45, 75, 90, 802, 24, 2, 66] 进行基数排序：

1. 个位排序：[170, 90, 802, 2, 24, 45, 75, 66]
2. 十位排序：[802, 2, 24, 45, 66, 170, 75, 90]
3. 百位排序：[2, 24, 45, 66, 75, 90, 170, 802]

---

3. 算法复杂度分析

3.1 查找算法复杂度对比

算法	平均时间复杂度	最坏时间复杂度	适用场景
二分查找	O(log n)	O(log n)	通用有序向量
插值查找	O(log log n)	O(n)	均匀分布数据
斐波那契查找	O(log n)	O(log n)	需要减少除法运算

3.2 排序算法复杂度对比

算法	时间复杂度	空间复杂度	稳定性
冒泡排序	O(n²)	O(1)	稳定
归并排序	O(n log n)	O(n)	稳定
基数排序	O(d·n)	O(n)	稳定

3.3 黄金比例与算法优化

斐波那契数列相邻项的比值趋近于黄金比例 φ = (1+√5)/2 ≈ 1.618，这种特性使得斐波那契查找在分割区间时能够达到接近最优的效果。

总结

本文详细介绍了三种重要的查找算法（二分查找、插值查找、斐波那契查找）和三种排序算法（冒泡排序、归并排序、基数排序）的原理、实现和复杂度分析。每种算法都有其适用的场景和优缺点：

• 查找算法：根据数据分布特性选择合适的算法
• 排序算法：根据稳定性要求和数据规模选择合适的方法
  理解这些基础算法的原理和实现，对于编写高效的程序和解决实际问题具有重要意义。