10 6 0 19 0 0 1 0 2 5 0 21 0 21 1 0 0 8 0 11 0 这是样例输入 0 2 0 0 0 1 5 0 6 0 8 0 11 0 19 0 21 1 21 0 这是样例输出,我应该怎么更改代码来达到样例要求
时间: 2023-12-31 12:07:16 浏览: 13
根据样例输出可以看出,需要将a数组和b数组同时进行排序,且排序的依据是a数组的元素大小。因此需要在划分函数中同时对a数组和b数组进行交换,而不是只交换b数组。具体来说,在交换r[i]和r[j]的同时,也需要交换q[i]和q[j]。修改后的代码如下所示:
```
#include <stdio.h>
#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;
int part(int* r, int* q, int low, int hight) //划分函数
{
int i = low, j = hight, pivot = r[low]; //基准元素
while (i < j)
{
while (i<j && r[j]>=pivot) //从右向左开始找一个 小于 pivot的数值
{
if(r[j] == pivot)
{
if(q[j] > q[low])
{
j--;
continue;
}
}
j--;
}
if (i <j)
{
swap(r[i], r[j]); //r[i]和r[j]交换后 i 向右移动一位
swap(q[i], q[j]);
}
while (i < j && r[i] <= pivot) //从左向右开始找一个 大于 pivot的数值
{
if(r[i] == pivot)
{
if(q[i] < q[low])
{
i++;
continue;
}
}
i++;
}
if (i < j)
{
swap(r[i], r[j]); //r[i]和r[j]交换后 i 向左移动一位
swap(q[i], q[j]);
}
}
return i; //返回最终划分完成后基准元素所在的位置
}
void Quicksort(int* r, int* q, int low, int hight) {
int mid;
if (low <hight)
{
mid = part(r, q, low, hight); // 返回基准元素位置
Quicksort(r, q, low, mid - 1); // 左区间递归快速排序
Quicksort(r, q, mid + 1, hight); // 右区间递归快速排序
}
}
int main() {
int a[100000];
int b[100000];
int N;
cin >> N;
for (int i = 0; i < N; i++)
{
cin >> a[i];
cin >> b[i];
}
Quicksort(a, b, 0, N - 1);
for (int i = 0; i < N; i++)
{
cout << a[i] << " ";
cout << b[i] << endl;
}
return 0;
}
```
需要注意的是,在划分函数中需要先判断r[j]是否等于pivot,如果相等,再判断q[j]和q[low]的大小关系,如果q[j]大于q[low],则需要继续向左移动j。同理,在判断r[i]时也需要先判断r[i]是否等于pivot,如果相等,再判断q[i]和q[low]的大小关系,如果q[i]小于q[low],则需要继续向右移动i。这样就可以满足题目要求,输出的a数组是按照从小到大排序的,而且如果有多个相同的数,b数组的顺序也可以满足题目要求。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)