【GESP】C++五级考试大纲知识点梳理, (5) 算法复杂度估算（多项式、对数）

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

void quickSort(int a[], int l, int r) {
    // 基准情况：当区间长度为1或更小时，直接返回
    if (l >= r) return;

    // partition操作的时间复杂度为O(n)
    // 每次选择一个基准值，将数组分为两部分
    int pivot = partition(a, l, r); // O(n)

    // 递归处理左右两个子数组
    // 每次递归将问题规模缩小一半左右
    // 递归树的深度为log n
    quickSort(a, l, pivot - 1);     // T(n/2)
    quickSort(a, pivot + 1, r);     // T(n/2)

    // 总体时间复杂度分析：
    // T(n) = 2T(n/2) + O(n)
    // 根据主定理，最终复杂度为O(n log n)
}

void mergeSort(int a[], int l, int r) {
    // 基准情况：当区间长度为1或更小时，直接返回
    if (l >= r) return;

    // 计算中点，将数组分成两半
    // 体现了分治思想，每次将问题规模缩小一半
    int mid = (l + r) / 2;

    // 递归处理左半部分
    // T(n/2) 复杂度
    mergeSort(a, l, mid);

    // 递归处理右半部分
    // T(n/2) 复杂度
    mergeSort(a, mid+1, r);

    // 合并两个有序数组
    // 时间复杂度为O(n)，需要遍历所有元素
    merge(a, l, mid, r); // O(n)

    // 总体时间复杂度分析：
    // T(n) = 2T(n/2) + O(n)
    // 根据主定理，最终复杂度为O(n log n)
}

void heapSort(int a[], int n) {
    // 构建最大堆
    // 从最后一个非叶子节点开始，向上调整
    // 时间复杂度为O(n)
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(a, n, i);
    }

    // 从堆中提取元素，构建有序数组
    // 每次提取根节点（最大值），然后调整堆
    // 时间复杂度为O(n log n)
    for (int i = n - 1; i > 0; i--) {
        // 交换根节点和当前最后一个节点
        swap(a[0], a[i]);
        // 对根节点进行调整，恢复最大堆性质
        heapify(a, i, 0);
    }
}