c - 同时对两个数组快速排序并行数组
问题描述
我有两个并行数组,一个 double a[] 和一个 int b[],我正在尝试使用快速排序对其进行排序。
我想按降序对第一个数组 a[] 进行排序,同时交换 b[] 的值。
同时,对于 a[] 的元素具有相同的值,b[] 的元素必须按升序排序。
我已经调整了以下代码,但我不知道如何实现最后一部分。
void qsort1(double a[], int b[], int lo, int hi) {
int h, l, p, t1;
double t;
if (lo < hi) {
l = lo;
h = hi;
p = a[hi];
do {
while ((l < h) && (a[l] <= p))
l = l+1;
while ((h > l) && (a[h] >= p))
h = h-1;
if (l < h) {
t = a[l];
a[l] = a[h];
a[h] = t;
t1 = b[l];
b[l] = b[h];
b[h] = t1;
}
} while (l < h);
a[hi] = a[l];
a[l] = p;
qsort1( a, b, lo, l-1 );
qsort1( a, b, l+1, hi );
}
}
例如:
开头的数组:
a[1] = 10 b[1] = 1
a[2] = 15 b[2] = 2
a[3] = 20 b[3] = 3
a[4] = 15 b[4] = 4
最后的数组:
a[1] = 20 b[1] = 3
a[2] = 15 b[2] = 2
a[3] = 15 b[3] = 4
a[4] = 10 b[4] = 1
解决方案
我会避免两个独立的数组。相反,我会创建一个包含一个双精度和一个整数的结构,并创建一个该结构的数组。好处有两点:
1) 数组可以通过标准 qsort 排序
2) 对双精度优先排序,双精度相等时对整数排序的要求,可以通过比较函数轻松实现。
它看起来像这样:
typedef struct
{
double a;
int b;
} SomeDataType;
int compar(const void * a, const void * b)
{
SomeDataType* pa = (SomeDataType*)a;
SomeDataType* pb = (SomeDataType*)b;
if (pa->a > pb->a) return -1;
if (pa->a < pb->a) return 1;
if (pa->b > pb->b) return 1;
if (pa->b < pb->b) return -1;
return 0;
}
void pd(SomeDataType* p, int n)
{
for(int i=0; i<n; ++i)
{
printf("%f - %d\n", p[i].a, p[i].b);
}
}
int main()
{
SomeDataType arr[] = {{10.0, 1}, {15.0, 2}, {20.0, 3}, {15.0, 4}};
pd(arr, 4);
qsort(arr, 4, sizeof(SomeDataType), compar);
printf("-------------------------\n");
pd(arr, 4);
return 0;
}
输出:
10.000000 - 1
15.000000 - 2
20.000000 - 3
15.000000 - 4
-------------------------
20.000000 - 3
15.000000 - 2
15.000000 - 4
10.000000 - 1
如果在程序中有两个单独的数组很重要,我仍然会使用qsort
一个结构数组。我会分 3 步进行排序。
1) 将数据从单个数组复制到结构数组
2)使用排序结构数组qsort
3) 将结构数组中的排序数据复制回各个数组
这可能看起来像:
typedef struct
{
double a;
int b;
} SomeDataType;
int compar(const void * a, const void * b)
{
SomeDataType* pa = (SomeDataType*)a;
SomeDataType* pb = (SomeDataType*)b;
if (pa->a > pb->a) return -1;
if (pa->a < pb->a) return 1;
if (pa->b > pb->b) return 1;
if (pa->b < pb->b) return -1;
return 0;
}
void qsort1(double a[], int b[], int lo, int hi)
{
if (lo < hi)
{
int num_elements = hi - lo + 1;
SomeDataType* p = malloc(num_elements * sizeof *p);
// Copy from individual arrays to array of structs
for(int i=0; i<num_elements; ++i)
{
p[i].a = a[lo+i];
p[i].b = b[lo+i];
}
// Sort array of structs
qsort(p, num_elements, sizeof *p, compar);
// Copy from array of structs back to individual arrays
for(int i=0; i<num_elements; ++i)
{
a[lo+i] = p[i].a;
b[lo+i] = p[i].b;
}
free(p);
}
}
void pa(double a[], int b[], int n)
{
for(int i=0; i<n; ++i)
{
printf("a[%d] = %f b[%d] = %d\n", i, a[i], i, b[i]);
}
}
int main()
{
double a[] = {10.0, 15.0, 20.0, 15.0};
int b[] = {1, 2, 3, 4};
pa(a, b, 4);
qsort1(a, b, 0, 3);
printf("-------------------------\n");
pa(a, b, 4);
return 0;
}
输出:
a[0] = 10.000000 b[0] = 1
a[1] = 15.000000 b[1] = 2
a[2] = 20.000000 b[2] = 3
a[3] = 15.000000 b[3] = 4
-------------------------
a[0] = 20.000000 b[0] = 3
a[1] = 15.000000 b[1] = 2
a[2] = 15.000000 b[2] = 4
a[3] = 10.000000 b[3] = 1
推荐阅读
- java - 如何在 thymeleaf 页面中显示来自 BindingResult.reject("message") 的消息
- matlab - 在 simscape 多体中建模 segway 机器人
- spring-boot - Spring Boot - 本地化到达自定义(DWR)AbstractController 的请求,本地化子线程,LocaleResolver 与 LocaleChangeInterceptor
- python - 如何将二维 numpy 数组中的所有数字转换为字符串?
- spring-boot - Spring Boot Maven 插件 > 2.4.x 构建镜像在 GitLab 注册表上发布
- sql-server - 无法使用特殊主体 'sa' - ant sql 任务
- html - 调整浏览器大小时,我的 div 容器溢出
- java - java.sql.SQLSyntaxErrorException: ORA-01797: 此运算符后面必须跟 ANY 或 ALL
- flutter - Flutter,Bloc,为什么MapEventToState中只使用Stream
- react-native - 没有幻灯片动画的介绍滑块