归并排序、快速排序选择的过程及复杂度分析

发布时间:2024年01月07日

归并排序、快速排序/选择的过程及复杂度分析

1 归并排序

归并排序首先递归划分数组直至一个元素,每次都是**“对半”划分**(不能保证每次划分的两个子区间内元素数量相等),时间复杂度稳定,然后从下往上进行归并处理

递归划分

递归划分的过程:

  • 递归第0层,n个数被划分为1个子区间
  • 递归第1层,将n个数划分为2个子区间
  • 递归第2层,将n个数划分为4个子区间

  • 递归的第log n层,将n个数划分为n个子区间

例如对于数组[5,2,3,4,1,8,7,6]l = 0, r = 7。**递归划分(自上而下)**如下图所示:

在这里插入图片描述

选取8个元素的数组为例是为了更好地看出划分的效果。显然并不是所有情况都能划分地这么“规整”,会存在划分的子区间内元素不等的情况,但是由于每次划分下标的选取都是采用的是(区间左下标+区间右下标)/2,所以总体来说,递归划分的深度为log n层。当区间内只有一个元素时,无法再进行划分,直接返回。

归并处理

**归并处理(自下而上)**的示意图如下:

在这里插入图片描述

圆弧表示这段区间内的排序操作,旁边的数字表示操作的顺序。排序使用的方法是归并(用一个临时数组合并两个有序数组),时间复杂度为O(n),空间复杂度为O(n)n为归并的元素个数,具体归并操作就不展开了,本文主要分析其过程和复杂度。

显然:

  • 在第2层中,共4个子区间,发生了4次排序,共排序8个元素。
  • 在第1层中,共2个子区间,发生了2次排序,共排序8个元素。
  • 在第0层中,共1个子区间,发生了1次排序,共排序8个元素。

即对于每一层的每一个子区间(最后一层不算,因为它每个区间只有一个元素,不需要排序),处理的时候都需要遍历一次区间中的每一个元素。

所以对于每一层来说,遍历个数都为n,复杂度为O(n)。而总共log n层,所以归并排序的时间复杂度为O(nlog n)

又因为每次归并过程中需要用到临时数组来存储元素,而且在第0层所需数组大小的最大,其大小为n;所以归并排序的空间复杂度为O(n)。(也可考虑其递归过程产生的log n层递归调用的空间复杂度)

代码

void merge(int l, int r){
    if(l >= r)	// 该子区间只有一个元素,直接返回
        return;
    
    int mid = (l + r) >> 1;		// 取分界点 mid = (l + r) / 2
    merge(l, mid);		// 左子区间为(l, mid)
    merge(mid + 1, r);		// 右子区间为(mid + 1, r)
    
    int tmp[r - l + 1] = {0};   // 临时数组,大小为区间长度
    int k = 0, i = l, j = mid + 1;  // k是已归并的元素数量,i是做子区间起点,j是右子区间起点
    
    while(i <= mid && j <= r){   // 归并操作,合并两个有序子区间
        if(a[i] < a[j])
            tmp[k++] = a[i++];
        else
            tmp[k++] = a[j++];
    }
    while(i <= mid)
        tmp[k++] = a[i++];
    while(j <= r)
        tmp[k++] = a[j++];
    
    for(int i = 0;i < k;i++)	// 更新一次数组,上层在此基础之上继续归并排序(自下而上)
        a[l + i] = tmp[i];
}

2 快速排序

快速排序也是利用分治的思想对各区间进行排序处理,时间复杂度不那么稳定,然后从上往下进行排序处理。与归并排序不同,快速排序不是每次将区间“对半”划分,而是按轴(值)划分,轴左边的数小于等于他,轴右边的数大于等于他。所以轴的选取非常重要,将会影响到他的时间复杂度。

快速排序有很多种模板,但是核心都是将区间分为两部分,再对子区间进行处理,直至区间不可分

  1. 有一种是将区间分为两部分:小于等于x的部分、大于等于x的部分

  2. 还有是将区间分为三部分,小于等于x的部分、x、大于等于x的部分(因为不会递归x的部分,所以也可以理解为分成了两部分)

*第2种方法,是本文使用的方法。因为他每一次划分都将数x放在了正确的位置上,笔者认为这样更好理解时间复杂度。*如下图所示:

  • 选取了奇数数组方便画图,每次选取最左边元素作为轴(也可选别的),且每次都会选取到区间的中位数;注意这不是完整的递归流程图,理论上排序是按前序遍历的顺序来排序的,请按照弧线数字顺序来看
  • 弧线表示一次排序操作,具体方法见代码旁边的数字表示这是第几次排序;第3层中的弧线没有排序操作,因为他只有一个元素会直接返回,这里花弧线主要是方便标顺序以及表示这个数的位置被确认了
  • 可见,第1层确定了1个元素的位置;第2层确定了2个元素的位置(注意不是同时确定的);…
  • 快排递归过程,与归并相反,是一个从上到下处理的过程。处理完当前区间,再处理子区间

在这里插入图片描述

如果每次选取轴都恰好能像上图一样使区间“对半”划分,则快速排序的递归划分的复杂度为log n,即划分最多log n层;对于每一层,执行上述的过程中都要遍历每一个元素,复杂度为O(n);这两点点和归并排序一样,即快速排序最好的总时间复杂度为O(n log n)

但是,每次都“对半”划分这个概率是否有点太低?甚至假如每次都选取了当前区间的最大/小值最为轴的话:

  • 递归的第0层,n个数被划分为1个子区间,每个子区间的数字个数为n

  • 递归的第1层,n个数被划分为2个子区间,每个子区间的数字个数为n-11;(那1个数即是最大/小值,他没有右/左子区间;后续同理)

  • 递归的第2层,n-1个数被划分为2个子区间,每个子区间的数字个数为n-21

  • 递归的第3层,n-2个数被划分为2个子区间,每个子区间的数字个数为n-31

  • 递归的第n-1层,2个数被划分为2个子区间,每个子区间的数字个数为11
  • 递归的第n层,1个数被划分为1个子区间,每个子区间的数字个数为1
  • (可以理解为每次划分得很极限,人家归并排序都一半一半分(即log n层),这里直接一个一个分,所以就要分n层咯)

对于每一层,处理的时候都需要遍历一次区间中的每一个元素,所以对于1~n层来说,遍历个数为nn-1n-2、…、21

所以时间复杂度最差为n + n-1 + ...+ 2 + 1等差数列求和为:n(1+n)/2,即O(n^2)?

空间复杂度主要是递归造成的栈空间的使用,最好情况,递归树的深度为log n;最坏情况,需要进行n次递归调用,其空间复杂度为O(n)

代码

// a[n]
// qsort(0, n - 1);
void qsort(int l, int r) {
    if(l >= r)
        return;
    int i = l, j = r;
    // 轴为 a[l]
    while(i < j) {
        while(i < j && a[j] >= a[l]) j--;  // 从右边开始选一个小于轴的数。注意要先从j开始找,因为如果a=[5,4,3,2,6],先从i找会导致5和6交换,原因就在于没有先使用右指针限制左指针的移动范围
        while(i < j && a[i] <= a[l]) i++;  // 从左边开始选一个大于轴的数
        swap(a[i], a[j]);    // 交换这两个不在正确区域的数
    }
    swap(a[i], a[l]);  // 把轴换到交界处,真的是轴
    
    qsort(l, i - 1);  // 左子区间
    qsort(i + 1, r);  // 右子区间
}

3 快速选择

从上面分析可知,每次排序都会确定一个数的位置,左边都是大于等于他的数,右边都是大于等于他的数。所以如果我需要前k小的数或者第k小的数,就可以根据每次确定的这个位置来选择下次递归的方向,相当于进行了剪枝。

例如,如果需要第5小的数。第一次我选取的轴恰好是第8小的数,说明此时,轴左边部分的数小于等于轴(即比第8小还小,第9,10,11...小),就算再递归这一部分,也是南辕北辙;所以递归右边大于等于轴部分才能接近第5小,后续同理。

所以理想情况下,每次只需要递归一边(约为上一次的一半),时间复杂度: n + n 2 + n 4 + . . . = n ( 1 + 1 2 + 1 4 + 1 8 . . . ) < 2 n n + \frac{n}{2} + \frac{n}{4}+ ... =n(1+\frac12+\frac14+\frac18...)<2n n+2n?+4n?+...=n(1+21?+41?+81?...)<2n,即O(n)

同理上节,最坏情况下复杂度为O(n^2)

要找第1小,第一次选到第10小(最大),选择靠近第1小的那边(也没有另一半来选撒),然后选到第9小…然后然后选到第8小…

即每次都脸黑地选取到区间最大/小值。

代码

// a[n]
void q_select(int l, int r, int &k) {
        if(l >= r)
            return;
        int i = l, j = r;
        while(i < j) {
            while(i < j && a[j] >= a[l]) j--;
            while(i < j && a[i] <= a[l]) i++;
            swap(a[i], a[j]);
        }
        swap(a[i], a[l]);  // 与上述快速排序一致
        
        if(i == k - 1)  // 恰好是
            return;
        if(i < k - 1)  // 判边
            q_select(i + 1, r, k);
        else
            q_select(l, i - 1, k);
    }
文章来源:https://blog.csdn.net/qq_45746571/article/details/135433812
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。