排序

• 1. 快速排序
• 2. 归并排序
• 3. 桶排序
• 4. 堆排序

1. 快速排序

时间复杂度：$O(nlog^n)$，最坏 $O(n^2)$ ，不稳定

• 基于分治法实现：

1. 确定分界点
2. 调整区间
3. 递归处理左右两段

// 快速排序模板
// l:左端点
// r:右端点
void quick_sort(int arr[],int l,int r) {
	if(l>=r)
		return;
	// 无符号右移一位等于除2
	int x=arr[l+r>>1]; // 找中间值
	// 遍历因子
	int i=l-1;
	int j=r+1;
	
	while(i<j) {
        // 把下面两个while中的"<"和">"换一下就是从大到小排序
		while(arr[++i]<x);
		while(arr[--j]>x);
		if(i<j)
			swap(arr[i],arr[j]);
	}
	// 分治法
	quick_sort(arr,l,j); // 排序左侧
	quick_sort(arr,j+1,r); // 排序右侧
}

2. 归并排序

时间复杂度妥妥的：$O(nlog^2)$，稳定

• 基于分治法实现：

1. 确定分界点
2. 递归把数据分成两段
3. 合二为一

// 归并排序模板
// arr[]:待排序数组
// l:排序左区间
// r:排序右区间
void merge_sort(int arr[],int l,int r) {
	if(l>=r)
		return; // 传入数据有误
	int mid=l+r>>1;
	// 递归将数据分成两段,回来时排序
	merge_sort(arr,l,mid);
	merge_sort(arr,mid+1,r);
	// 回来时的操作
	// k:temp数组的遍历因子/
	// i:第一段的最左端
	// j:第二段的最左端
	int k=0,i=l,j=mid+1;
	// 从小到大排序
	while(i<=mid && j<=r) {
		if(arr[i]<=arr[j])
			temp[k++]=arr[i++]; 
		else
			temp[k++]=arr[j++];
	}
	// 把未排好的直接添加到temp末尾,下面两种情况二选一
	while(i<=mid)
		temp[k++]=arr[i++];
	while(j<=r)
		temp[k++]=arr[j++];
	
	// 此时l和r是形参传递过来的l和r
	// j:temp的遍历因子,目的是赋值
	for(int i=l,j=0;i<=r;i++,j++) {
		arr[i]=temp[j];
	}
}

例题：P1908 逆序对 - 洛谷

• 该题为利用归并排序求解逆序对的问题，携带了如何输出逆序对，但是没有解决以字典顺序输出逆序对的问题，可能要用其他算法。

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+5;
int arr[maxn];
int temp[maxn]; // 辅助数组
long long res; // n=5e5,最大对数可能超过1e10*2
void merge_sort(int arr[],int l,int r) {
	if(l>=r)
		return;
	int mid=l+r>>1;
	// 先分
	merge_sort(arr,l,mid);
	merge_sort(arr,mid+1,r);
	// 合并
	int k=0,i=l,j=mid+1;
	while(i<=mid && j<=r){
		if(arr[i]<=arr[j])
			temp[k++]=arr[i++];
		else {
			// 输出逆序对
//			for(int m=i;m<=mid;m++) {
//				cout<<"<"<<arr[m]<<","<<arr[j]<<">"<<'\n';
//			}
			temp[k++]=arr[j++];
			// 如果arr[i]比arr[j]大了,那么arr[i]右边的也比它大
			res+=(mid-i+1); // 一共mid-i+1个
		}
	}
	while(i<=mid)
		temp[k++]=arr[i++];
	while(j<=r)
		temp[k++]=arr[j++];
	// 赋值
	for(int i=l,j=0;i<=r;i++,j++) {
		arr[i]=temp[j];
	}
}
int main() {
	int n;
	cin>>n;
	// test
	for(int i=1;i<=n;i++) {
		cin>>arr[i];
	}
	merge_sort(arr,1,n);
//	for(int i=1;i<=n;i++) {
//		cout<<arr[i]<<' ';
//	}
//	cout<<'\n';
	cout<<res;
	return 0;
}

3. 桶排序

时间复杂度：$O(n+k)$，$n$ 是输入数据量，$k$ 是桶的个数；空间复杂度：$O(k)$，额外分配的内存就是 $k$ 个桶的空间

1. 装桶
2. 倒桶

• 注意：桶排序容易超出最大值（字典思想），通常每个值都特别限定的范围时用桶排序，如每个值都限定在 $[0,50]$ 之间。

const int MAX_NUM=1e8; // 最大值不能超过1e8
int sum[MAX_NUM]; // 值域
void bucket_sort(int arr[]) {
	// 字典装桶
	for(int i=1;i<=n;i++)
		sum[arr[i]]++; // 把数组的值装进桶
	// 倒出
	for(int i=1,j=1;j<=n;i++) {
		// 当sum[i]>=1时才进入while
		while(sum[i]--)
			arr[j++]=i; // 下标即是值,对arr重新赋值排序后的结果
	}
}

• 桶排序完整案例：

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;

const int maxn=1e4+4; // 数字最大1e4个
const int maxv=1e4+4; // 每个数字的值最大1e4
int arr[maxv]; // 桶

int main() {
	int n;
	cin>>n;
	int temp;
	// 字典装桶
	for(int i=1;i<=n;i++) {
		cin>>temp;
		arr[temp]++;
	}
	// 从大到小倒桶
	for(int i=maxv;i>=0;i--) {
		// 该字符打印arr[i]次,如果j=0则不进入
		for(int j=0;j<arr[i];j++) // 注意这层循环的遍历次数由i来决定,所以这两层循环的时间复杂度都取决于i
			cout<<i<<' ';
	}
	return 0;
}

4. 堆排序

时间复杂度：$O(nlog^n)$

• 堆（完全二叉树）：有大根堆和小根堆之分。

1. 求堆最小值：$q[1]$
2. 删除最小值：$q[1]=q[size]$，$down(1)$
3. 输出堆顶，删除堆顶，长度减一，$down(1)$

• 注：$down$ 是调整堆的操作，即与自己的孩子比较，将自己的值与其中最小且比自身更小的值交换。

// 堆排序模板
// sz:当前堆大小
// t:当前堆
int sz; 
void down(int u) {
	int t=u; 
	// 如果左孩子在范围内且值更小
	if(2*u<=sz && arr4[t]>arr4[2*u])
		t=2*u;
	if(2*u+1<=sz && arr4[t]>arr4[2*u+1])
		t=2*u+1;
	if(t!=u) {
		swap(arr4[t],arr4[u]);
		down(t); // 递归调整
	}
}

• 主函数部分：

// 测试堆排序
for(int i=1;i<=n;i++) {
    cin>>arr4[i];
}
sz=n; // 初始堆大小
// 建立小根堆
// n/2是最后一个有孩子的节点
for(int i=n/2;i;i--)
    down(i);
while(n--) {
    cout<<arr4[1]<<" "; // 输出堆顶
    arr4[1]=arr4[sz--]; // 调整堆顶
    down(1); // 调整堆
}

打赏