复兴无基础第二十八课 排序进阶
2025-11-23 15:28:02
发布于：上海
0阅读
0回复
0点赞
T1【归并排序】升序
clude<iostream>
using namespace std;
int n , a[1010] , temp[1010];
void MergeSort(int l , int r)
{
//2.1、递归的结束条件:只有一个数，就不用再递归下去，直接返回
if(l == r)
return;
//2.2、找到中间位置，递归处理左半部分，递归处理右半部分
int mid = (l + r) / 2;
MergeSort(l , mid);
MergeSort(mid + 1 , r);
//3、合并，两个序列分别为[l,mid] 和 [mid+1,r]，从最左边开始，依次比较，小的数放入结果数组temp，下标右移
int i = l, j = mid + 1, k = l;
while(i <=mid && j <= r)
{
if(a[i] <= a[j])
temp[k++] = a[i++];
else
temp[k++] = a[j++];
}
//3.1、判断两个序列是否有剩余，有剩余的，全部放入结果数组 temp
while(i <= mid)
temp[k++] = a[i++];
while(j <= r)
temp[k++] = a[j++];
//4、把结果数组 temp 重新赋给 a 数组
for(int i = l; i <= r; i++)
a[i] = temp[i];
//5、输出a数组
for(int i = 1; i <= n; i++)
cout << a[i] << " ";
cout << endl;
}
int main()
{
//1、定义变量 n 和数组
cin >> n;
for(int i = 1; i <= n; i++)
cin >> a[i];
//2、划分，左端点为 1，右端点为 n，递归处理
MergeSort(1 , n);
return 0;
}
T2【快速排序】升序
#include <iostream>
using namespace std;
const int N = 1e3 + 10;
int a[N];
int n;
int partition(int a[], int l, int r)
{
//3、找枢轴的位置，保证枢轴左边的都比枢轴小，枢轴右边的都比枢轴大
//3.1、l和r分别为左右端点，k为枢轴
int k = a[l]; //枢轴
while (l < r)
{
//3.2、右边的元素比枢轴大，右端点左移
while (l < r && a[r] >= k)
r--;
a[l] = a[r];
//3.3、左边的元素比枢轴小，左端点右移
while (l < r && a[l] <= k)
l++;
a[r] = a[l];
}
a[l] = k;
return l; //返回枢轴位置
}
//数组 a 的[l,r] 排序(升序）
void QuickSort(int a[], int l, int r)
{
//2.1、结束条件
if (l >= r) return; //只有一个元素，不能划分，返回
//2.2、找到一趟快速排序后，记录枢轴的位置
int pos = partition(a, l, r);//划分后枢轴的位置
//2.3、输出一次的结果
for(int i = 1; i <= n; i++)
cout << a[i] << " ";
cout << endl;
//2.4、递归处理左右两边
QuickSort(a, l, pos - 1);
QuickSort(a, pos + 1, r);
}
int main()
{
//1、定义变量 n 和数组，输入
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
//2、快速排序，递归处理
QuickSort(a, 1, n);
return 0;
}
T3第k小的数
#include <iostream>
using namespace std;
const int N = 5e6 + 10;
int a[N];
int n, k;
int partition(int a[], int l, int r)
{
//3、找到枢轴的位置，返回
int m = a[l]; //枢轴
while (l < r)
{
while (l < r && a[r] >= m) r--;
a[l] = a[r];
while (l < r && a[l] <= m) l++;
a[r] = a[l];
}
a[l] = m;
return l; //返回枢轴位置
}
//数组 a 的[l,r] 排序(升序）
void QuickSort(int a[], int l, int r)
{
//2.1、记录枢轴的位置
int pos = partition(a, l, r);//划分后枢轴的位置 划分后将数组分为三块，l~pos-1、pos、pos+1~r
//2.2、k 在枢轴的左半部分
if(k < pos)
QuickSort(a, l, pos - 1); //在左边只需搜左区间
//2.3、k 在枢轴的右半部分
else if(k > pos)
QuickSort(a, pos + 1, r); //在右边只需搜右区间
//2.4、k就是枢轴的位置
else //在中间的话直接输出
{
printf("%d",a[k]);
return;
}
}
int main()
{
//1、定义变量n、k和数组，进行输入
scanf("%d%d",&n,&k);
for (int i = 0; i < n; i++)
scanf("%d",&a[i]);
//2、快速排序，找第k小的数
QuickSort(a, 0, n-1);
return 0;
}
T4逆序对
#include <iostream>
using namespace std;
const int N = 5e5 + 10;
int a[N], tmp[N];
long long n, ans;
//a的[L1,R1] 和 [L2,R2] 做归并
void Merge(int a[], int L1, int R1, int L2, int R2)
{
//3、两个序列依次合并
int i = L1, j = L2;
int cnt = 0;
while (i <= R1 && j <= R2)
{
if (a[i] <= a[j])
tmp[cnt++] = a[i++];
else
{
//3.1、右区间的a[j]大于左区间的a[i],则a[j]与左区间的i~R1的所有数全部构成逆序对
tmp[cnt++] = a[j++];
ans += R1 - i + 1;
}
}
//左半段剩余的元素
while (i <= R1) tmp[cnt++] = a[i++];
//右半段剩余的元素
while (j <= R2) tmp[cnt++] = a[j++];
//0~cnt-1，tmp复制到a
for (int i = 0; i < cnt; i++)
{
a[L1 + i] = tmp[i];
}
}
void MergeSort(int a[], int l, int r)
{
if (l >= r)
return; //只有一个元素，划分结束，返回
int mid = (l + r) / 2;
MergeSort(a, l, mid); //递归处理左半边[l,mid]
MergeSort(a, mid + 1, r);//递归处理右半边[mid+1,r]
Merge(a, l, mid, mid + 1, r);//两个半边做归并
}
int main()
{
//1、定义变量、数组，进行输入
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
//2、归并排序，递归处理
MergeSort(a, 1, n);
cout << ans;
return 0;
}
这里空空如也
有帮助，赞一个