快速排序、归并排序与二分法

本文总结三类基础但非常核心的算法：快速排序、归并排序与二分法。这三者几乎覆盖了大部分基础算法题的核心思想：分治 + 单调性。

一、快速排序（Quick Sort）

1. 基本思想

快速排序的核心思想是：

选取一个基准值（pivot），通过一次划分操作，使得当前区间被分为两部分：左侧元素不大于 pivot，右侧元素不小于 pivot。

然后对左右两个子区间递归执行相同操作，直到区间长度为 0 或 1。

需要注意：

pivot 不一定会被放到最终有序位置
递归依据的是分区后的区间边界，而不是 pivot 的位置

2. 双指针分区法（Hoare Partition）

常见实现是双指针法：

左指针从左向右找 ≥ pivot 的元素
右指针从右向左找 ≤ pivot 的元素
找到后交换
重复直到指针相遇

3. 代码实现（C语言）

#include <stdio.h>

void quicksort(int left, int right, int *array){
    // 递归终止条件
    if(left >= right) return;

    int i = left - 1;
    int j = right + 1;
    int pivot = array[(left + right) / 2];
    int temp;

    while(i < j){
        do i++; while(array[i] < pivot);
        do j--; while(array[j] > pivot);

        if(i < j){
            temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }

    // 递归左右区间
    quicksort(left, j, array);
    quicksort(j + 1, right, array);
}

int main(){
    int n;
    scanf("%d", &n);

    int array[n];
    for(int i = 0; i < n; i++) scanf("%d", &array[i]);

    quicksort(0, n - 1, array);

    for(int i = 0; i < n; i++) printf("%d ", array[i]);

    return 0;
}

4. 时间复杂度

平均复杂度：(O(n \log n))
最坏情况：(O(n^2))

二、归并排序（Merge Sort）

1. 基本思想

归并排序基于分治思想，其流程为：

将数组划分为左右两个子区间
递归地对左右区间排序
将两个有序区间合并成一个有序区间

关键点在于：

如果两个数组已经有序，可以在 (O(n)) 时间内完成合并。

2. 核心理解

单个元素的数组一定是有序的
递归到底后，从底向上逐层合并
每一层都保证局部有序

3. 代码实现（C语言）

#include <stdio.h>

void mergesort(int left, int right, int *array, int *temp){
    // 递归终止条件
    if(left >= right) return;

    int mid = (left + right) / 2;

    // 递归排序
    mergesort(left, mid, array, temp);
    mergesort(mid + 1, right, array, temp);

    // 合并两个有序子区间
    int i = left;
    int j = mid + 1;
    int k = left;

    while(i <= mid && j <= right){
        if(array[i] <= array[j]){
            temp[k] = array[i];
            i++;
        }
        else{
            temp[k] = array[j];
            j++;
        }
        k++;
    }

    // 处理剩余部分
    while(i <= mid){
        temp[k] = array[i];
        i++;
        k++;
    }

    while(j <= right){
        temp[k] = array[j];
        j++;
        k++;
    }

    // 写回原数组
    for(int p = left; p <= right; p++) array[p] = temp[p];
}

int main(){
    int n;
    scanf("%d", &n);

    int array[n], temp[n];
    for(int i = 0; i < n; i++) scanf("%d", &array[i]);

    mergesort(0, n - 1, array, temp);

    for(int i = 0; i < n; i++) printf("%d ", array[i]);

    return 0;
}

4. 时间复杂度与特点

时间复杂度：(O(n \log n))（稳定）
空间复杂度：(O(n))
稳定排序

三、二分法（Binary Search）

1. 基本思想

二分法的核心是：

利用有序性或单调性，每次排除一半不可能的区间，从而缩小搜索范围。

二分不仅用于查找某个数，还常用于：

查找边界
查找满足条件的最小/最大值
答案二分

2. 常见两类问题

1）查找某个值是否存在

2）查找边界（最重要）

例如：

第一个 ≥ x 的位置（lower_bound）
第一个 > x 的位置（upper_bound）

3. lower_bound 与 upper_bound

定义

lower_bound(x)：第一个 ≥ x 的位置
upper_bound(x)：第一个 > x 的位置

4. 代码实现（C语言）

int find_lower_bound(int num, int left, int right, int bound, int* array){
    /*用于查找序列中第一个大于等于num的数的index*/
    // 递归终止条件
    if(left > right) return bound;
    int mid = (left + right) / 2;
    // 注意这里是大于等于
    if(array[mid] >= num){
            bound = mid;
            return find_lower_bound(num, left, mid - 1, bound, array);
    }
    else{
            return find_lower_bound(num, mid + 1, right, bound, array);
    }
}

int find_upper_bound(int num, int left, int right, int bound, int* array){
    /*用于查找序列中第一个大于num的数的index*/
    // 递归终止条件
    if(left > right) return bound;
    int mid = (left + right) / 2;
    // 注意这里是大于
    if(array[mid] > num){
            bound = mid;
            return find_upper_bound(num, left, mid - 1, bound, array);
    }
    else{
            return find_upper_bound(num, mid + 1, right, bound, array);
    }
}

5. 调用方式

int lower = find_lower_bound(x, 0, n - 1, n, array);
int upper = find_upper_bound(x, 0, n - 1, n, array);

6. 应用：判断是否存在 & 统计出现次数

// 判断是否存在
if(lower < n && array[lower] == x){
    // 存在
}

// 统计出现次数
int count = upper - lower;

四、总结

算法	核心思想	时间复杂度	特点
快速排序	分区 + 递归	平均 (O(n \log n))	原地排序，不稳定
归并排序	分治 + 合并	(O(n \log n))	稳定，需要额外空间
二分法	单调性 + 缩区间	(O(\log n))	关键在边界处理