平行数组解决数组排序后编号

Question

麻烦写出代码并附上每一句的解析，不太懂这部分内容，也请具体解释如何使相同数字编号相同

Answer 1

本答案参考多次询问ChatGPT-3.5后选择的最佳回答，若是满意，还请采纳，谢谢。

在C语言中，使用平行数组（也称为辅助数组）来解决数组排序后编号问题是一种常见的方法。这种方法的核心思想是使用一个辅助数组来记录原数组中元素的索引，然后根据这个索引数组对原数组进行排序，这样即使元素的值相同，它们的编号也会保持一致。

下面是一个具体的代码示例，以及每一句的解析：

#include <stdio.h>
#include <stdlib.h>

// 比较函数，用于qsort
int compare(const void *a, const void *b) {
    int ai = *(const int *)a;
    int bi = *(const int *)b;
    return ai - bi;
}

int main() {
    int arr[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5}; // 原始数组
    int idx[sizeof(arr) / sizeof(arr[0])]; // 辅助数组，用于存储索引
    int n = sizeof(arr) / sizeof(arr[0]); // 数组元素个数
    int sorted_arr[sizeof(arr) / sizeof(arr[0])]; // 排序后的数组

    // 初始化辅助数组，存储索引
    for (int i = 0; i < n; i++) {
        idx[i] = i;
    }

    // 使用qsort进行排序，传入辅助数组
    qsort(idx, n, sizeof(int), compare);

    // 根据辅助数组的索引，重新排列原数组
    for (int i = 0; i < n; i++) {
        sorted_arr[i] = arr[idx[i]];
    }

    // 打印排序后的数组和对应的编号
    for (int i = 0; i < n; i++) {
        printf("Element: %d, Index: %d\n", sorted_arr[i], idx[i]);
    }

    return 0;
}

解析：

• #include <stdio.h> 和 #include <stdlib.h>：包含标准输入输出库和标准库，后者包含了qsort函数。
• int compare(const void *a, const void *b)：这是一个比较函数，用于qsort。它接受两个const void *类型的参数，将它们转换为int类型，并返回它们的差值，用于比较。
• int main()：主函数。
• int arr[]：声明并初始化原始数组。
• int idx[]：声明辅助数组，用于存储每个元素的索引。
• int n：计算数组中元素的个数。
• int sorted_arr[]：声明一个数组，用于存储排序后的元素。
• for (int i = 0; i < n; i++) { idx[i] = i; }：初始化辅助数组，使其元素值等于它们的索引。
• qsort(idx, n, sizeof(int), compare);：使用qsort对辅助数组进行排序，实际上是根据辅助数组的值（即索引）对原数组进行排序。
• for (int i = 0; i < n; i++) { sorted_arr[i] = arr[idx[i]]; }：根据辅助数组的索引，重新排列原数组。
• for (int i = 0; i < n; i++) { printf("Element: %d, Index: %d\n", sorted_arr[i], idx[i]); }：打印排序后的数组和对应的编号。

通过这种方法，即使原数组中有相同的数字，它们的编号也会保持一致，因为在排序过程中，我们是根据元素的索引（即它们在原数组中的位置）来排序的。