快速排序与归并排序时间复杂度：递归与非递归双重解析

慢慢来

发布时间：2026-10-15| 4人浏览过

原创

面试中常考归并排序和快速排序的时间复杂度，知其然更需知其所以然。本文通过非递归代码视角和递归树逻辑，深入剖析这两种核心排序算法的复杂度来源，解释为何归并排序稳定在 O(nlogn)，而快速排序则在 O(nlogn) 到 O(n^2) 之间波动。

归并排序的时间复杂度推导

归并排序的时间复杂度为 O(nlogn)。这一结论可以通过递归过程和迭代过程两个维度来验证。

第1步：基于递归树的层数分析

假设对包含 n 个数的序列进行归并排序，递归划分过程如下：

第一层将 n 个数划分为 2 个子区间，每个区间大小 n/2；
第二层继续划分子区间，得到 4 个区间，大小为 n/4；
以此类推，直到第 logn 层，区间长度缩减为 1。

在自底向上的合并过程中，每一层都需要遍历当前的所有元素以完成合并。
- 最底层：合并 n/2 次，遍历所有 n 个元素，复杂度 O(n)。
- 倒数第二层：合并次数减半但区间变大，总元素仍为 n，复杂度同样为 O(n)。

由于总共存在 logn 层，且每层耗时 O(n)，因此总时间复杂度为 O(n × logn)。

第2步：基于非递归代码的结构验证

通过迭代方式实现归并排序可以更直观地看到层级的变化。以下是关键的伪代码结构：

/**
 * 此方法用来定义子区间大小，子区间大小从1->2->4->8 ... ->n/2
 * 可以近似地认为进行了logn次
 */
public static void merge(int[] arr) {
    // 关键点1：划分子区间，每一次的子区间长度是上一次的两倍，所以这个循环需要执行logn次
    for(int i = 1;i<arr.length;i *= 2){
        // 关键点2：此方法每次执行的时间复杂度为O（n），具体看下方
        mergeSort(arr,i);
    }
}
/**
 * 以下方法，每次执行的时间复杂度都是O（n），
 * 因为需要将arr数组的每gap个数子，作为一个子区间，
 * 然后对相邻的两个子区间执行归并排序的merge操作，
 * 所以在这个方法中，arr数组中的每一个数都会在merge操作中，
 * 被处理一次，所以下面这个方法的时间复杂度为O（n）
 */
public static void mergeSort(int[] arr, int gap) {
    int[] tmp = new int[arr.length];
    int index = 0;
    int start1 = 0;
    int end1 = start1 + gap - 1;
    int start2 = end1 + 1;
    int end2 = (start2 + gap - 1)>=arr.length?arr.length-1:start2+gap-1;
    while(start2<arr.length){
        while(start1<=end1&&start2<=end2){
            if(arr[start1]<arr[start2]){
                tmp[index++] = arr[start1++];
            }else{
                tmp[index++] = arr[start2++];
            }
        }
        while(start1<=end1){
            tmp[index++] = arr[start1++];
        }
        while(start2<=end2){
            tmp[index++] = arr[start2++];
        }
        start1 = end2+1;
        end1 = start1 + gap - 1;
        start2 = end1 + 1;
        end2 = (start2 + gap - 1)>=arr.length?arr.length-1:start2+gap-1;
    }
    while(start1<arr.length){
        tmp[index++] = arr[start1++];
    }
    for(int j = 0;j<tmp.length;j++){
        arr[j] = tmp[j];
    }
}

上述代码中，外层 for 循环控制子区间大小的倍增（i *= 2），共执行 logn 次。内层的 mergeSort 方法负责当前规模下的线性扫描合并，时间复杂度为 O(n)。二者相乘，结果依然为 O(nlogn)。