[Note] 排序体系

[L4] 排序体系

1. 生态位

• 识别:
  1. 题面要求统计“逆序对”或“偏序关系”。
  2. 需要对带有多个权值的对象进行“稳定排序”。
  3. 在 $O(N)$ 期望时间内查询第 $K$ 大数。
• 地位: 基础算法，本质是消除序列中的 逆序对。
• 用途:
  • 归并排序: 解决“偏序计数”（如统计逆序对），是 CDQ 分治的原型。
  • 快速排序: 原地排序，同样是基于分治的 $N \log N$ 高效排序。

2. 逻辑支点

2.1 核心原理: 排序即逆序对清空

逆序对是什么？ 类似 $i < j, a[i] > a[j]$ 的这组 $(i,j)$。

引入：冒泡排序，最经典的排序算法，复杂度为 $O(N^2)$。

因为每次只处理相邻的两个数，而不影响其他数，所以每一次交换都是 $-1$ 逆序对。
通俗来说，冒泡排序交换元素的次数 $\iff$ 逆序对的数量。

2.2 分治思想

1. 快速排序：重分轻合

   • 中译中：选一个基准点(Pivot)，把比它大的全扔左边，比它小的全扔右边。
   • 因为划分完，基准点确定，左右区间互不干扰，所以核心复杂度在划分阶段。

2. 归并排序：轻分重合

   • 中译中：把区间折半，然后让左右子区间排序，接着再把左右区间合并。
   • 因为划分固定，所以复杂度稳定，重点在合并操作上。

3. 逆序对：

   • 归并排序的另一大价值在于，它可以在排序的过程中，同时统计逆序对个数。
   • 假设左区间 $L$ 和右区间 $R$ 都已经有序了。
   • 当我们合并时，如果 $a[i] > a[j]$，因为左区间 $L$ 是递增的。
   • 所以从 $i$ 到 $mid$ 的所有数都比 $j$ 大。
   • 那么直接就算出了 $mid - i + 1$ 个逆序对，实现高效降维。

2.3 STL

一般来说，竞赛中没有额外任务的排序通常采用 std::sort 函数来解决。

下面我简要介绍一下这个函数。

• 头文件 `#include
• 调用 std::sort( 首地址，末地址，自定义函数 )

▶

Sort函数简要介绍

#include <algorithm>
using namespace std;

const int maxn = 1e5 + 50;
int a[maxn];
int n;

struct Student {
	int id;
	int score;
} b[maxn];

bool cmp( int a, int b )
{
	return a > b;
}

// 此处逻辑为，先按照分数从大到小排序，
// 若分数相同，按照学号从小到大排序。
bool cmp1( Student a, Student b )
{
	if( a.score != b.score )
		return a.score > b.score;
	return a.id < b.id;
}

int main( )
{
	cin >> n;
	for( int i = 1; i <= n; ++ i )
	{
		cin >> a[i];
	}	
	
	sort( a + 1, a + n + 1 );       // 默认从小到大排序 a < b
	sort( a + 1, a + n + 1, cmp );  // 自定义函数从大到小排序 a > b
	sort( a + 1, a + n + 1, greater<int>() ) // 内置函数，从大到小排序
	
	for( int i = 0; i < n; ++ i )
	{
		cin >> b[i].id >> b[i].score;
	}

	sort( b + 0, b + n, cmp1 );	    // 结构体同样也能用自定义函数排序
	return 0;
}

3. 实战部署

▶

归并排序

int a[maxn], tmp[maxn];
long long ans = 0;

void merge_sort( int l, int r )
{
	if( l >= r ) return ;
	int mid = ( l + r ) >> 1;
	
	merge_sort( l, mid );
	merge_sort( mid + 1, r );
	
	int i = 1, j = mid + 1, k = 0;
	while( i <= mid && j <= r )
	{
		if( a[i] <= a[j] )
		{
			tmp[k ++] = a[i ++];
		}
		else
		{
			tmp[k ++] = a[j ++];
			// 若加上这一行，则同时统计逆序对数量。
			ans += (long long)( mid - i + 1 );
		}
	}
	
	while( i <= mid ) tmp[k ++] = a[i ++];
	while( j <= r ) tmp[k ++] = a[j ++];
	
	for( int p = 0; p < k; ++ p )
	{
		a[l + p] = tmp[p];
	}
}

▶

快速排序

void quick_sort( int l, int r )
{
    if( l >= r ) return;
    
	int mid = a[( l + r ) >> 1];
    int i = l - 1, j = r + 1;
    
    while( i < j )
    {
	    do i ++; while( a[i] < a[mid] );
	    do j --; while( a[j] > a[mid] );
        if( i < j ) swap( a[i], a[j] );
    }
    quick_sort( l, j );
    quick_sort( j + 1, r );
}

4. 知识关联

• 母题:

  • P1908 逆序对 BIT: 归并排序计算逆序对典例（不过我这题采用了另一种写法。

• 关联笔记:

  • 浅谈二分答案：排序有时能暴露参数化判定所需的顺序与单调结构。

  • 降维技巧: 处理权值过大但只关心相对大小时的必备操作。

  • [[CDQ 分治]]: 归并排序在高维偏序下的“进化体”。