数据结构与算法基础——快速排序与归并排序

前言

最近在复习数据结构，顺便整理之前刷题的一些模板和技巧，希望对大家都有帮助，博客会侧重讲解的是OJ代码实现，理论部分偏少但也会写一些自己的理解。
在之前大二上数据结构的时候我也有写过一个关于排序的专题介绍数据结构复习——内部排序

快速排序

快速排序主要就是通过选取一个基准点，将一个区间内的数分成大于和小于两个部分，然后对左右区间再进行上述操作，直到子区间的长度为空为止。快速排序是不稳定的排序，如果需要变成稳定排序通过双关键字排序即可，通过下标控制绝对大小就能得到稳定的排序结果。
快速排序分三步走：

• 确定分界点
• 调整左右区间
• 递归处理左右子区间

在代码实现当中，我们一般选取中间分位点会比较好，这样划分的区间比较平均。在遍历的过程当中每次调整区间的时间是$O(n)$，而区间递归的深度类似二叉树是$O(logn)$
在最好情况下，对于递归型的算法，我们利用主定理公式来计算快速排序时间复杂度得到$O(nlogn)$
$$
T(n) = 2 T\left(\frac{n}{2}\right)+\Theta(n)
$$
当然在最坏情况下，也就是数组是有序或者逆序的情况下，我们如果选择左右端点作为基准点，那么整个算法就相当于冒泡排序，递归的层数也就变成了$n$，则最坏时间复杂度为$O(n^2)$

代码实现

void quick_sort(int[] q,int l,int r)
{
	if(l>=r) return;
	// 1.确定分界点
	int i = l - 1, j = r + 1, mid = q[l + r >> 1];
	// 2.调整左右区间
	while(i<j)
	{
		do i++; while(q[i]<mid);
		do j--; while(q[j]>mid);
		if(i<j) swap(q[i],q[j]);
	}
	//3.递归处理左右子区间
	quick_sort(l,j);
	quick_sort(j+1,r);
}

经典例题

洛谷P1177 【模板】快速排序

归并排序

归并排序也是基于分治的思想，每次将区间对半分，逐步递归合并有序化子区间，最终实现所有的左右区间的有序归并，但是跟快速排序不同的是，我们需要开一个辅助数组来存储有序的部分，所以时间复杂度为$O(nlogn)$。归并排序是稳定的排序，在元素相等情况下我们总是放入数组下标较小的元素。
归并排序分三步走：

• 确定分界点
• 递归处理子序列
• 合并有序序列

代码实现

const int N=100010;
int a[N],tmp[N];
void merge_sort(int q[],int l,int r)
{
    if(l>=r)
        return;
    //确定分界点
    int mid = l + r >> 1;

    //递归处理子序列
    merge_sort(q,l,mid);
    merge_sort(q,mid+1,r);

    //合并有序序列
    int k = l,i = l,j = mid + 1;
    while(i <= mid && j <= r)
    {
        if(q[i]<=q[j])// 取等号，保证归并排序的稳定性
            tmp[k++]=q[i++];
        else
            tmp[k++]=q[j++];
    }

    while(i<=mid) 
        tmp[k++]=q[i++];
    while(j<=r) 
        tmp[k++]=q[j++];

    for(i=l;i<=r;i++)
        q[i]=tmp[i];
}

经典例题

AcWing 787. 归并排序
AcWing 788. 逆序对的数量

排序相关时间复杂度整理