PTA 7-224 sdut-C语言实验-排序问题

输入10个整数，将它们从小到大排序后输出，并给出现在每个元素在原来序列中的位置。

输入格式:

输入数据有一行，包含10个整数，用空格分开。

输出格式:

输出数据有两行，第一行为排序后的序列，第二行为排序后各个元素在原来序列中的位置。

输入样例:

1 2 3 5 4 6 8 9 10 7

输出样例:

在这里给出相应的输出。例如：

1 2 3 4 5 6 7 8 9 10
1 2 3 5 4 6 10 7 8 9

 这段代码没有考虑数组中可能存在相同元素的情况，如果数组中有重复的元素，该程序只会输出找到的第一个匹配元素的位置。

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

#define N 10 // 定义常量N为10，表示数组的大小

// 自定义比较函数，用于qsort函数中比较两个整数的大小
int cmp_int(const void* e1,const void* e2)
{
    return *(int*)e1-*(int*)e2;
}

int main()
{
    int arr[N]; 
    int arr2[N]; // 数组arr2，存放arr数组的副本

  
    for(int i=0; i<N; i++)
    {
        scanf("%d", &arr[i]);
        arr2[i] = arr[i];
    }

    // 使用qsort函数对arr2数组进行排序，排序依据是cmp_int函数
    qsort(arr2, N, sizeof(int), cmp_int);

    // 输出排序后的arr2数组
    for(int i=0; i<N; i++)
    {
        if(i == N-1) 
            printf("%d", arr2[i]);
        else
            printf("%d ", arr2[i]); 
    }
    printf("\n"); 

    // 遍历排序后的arr2数组，找出每个元素在原始arr数组中的位置
    for(int i=0; i<N; i++) 
    {
        for(int j=0; j<N; j++) 
        {
            if(arr2[i] == arr[j]) // 找到匹配的元素
            {
                if(i == N-1) 
                    printf("%d", j+1); 
                else
                    printf("%d ", j+1);
                break; // 找到匹配退出内层循环
            }
        }
    }
    return 0;
}

改进代码思路：

1.冒泡排序，并且同时对两个数组进行操作：一个是实际存储数据的数组 `arr`，另一个是用于跟踪原始位置的数组 `index`

2. 数组 `arr` 用于存储用户输入的整数，数组 `index` 初始时被设置为 `{1, 2, 3, ..., 10}`，表示每个元素的初始位置

4. 程序调用 `bubble_sort` 函数对数组 `arr` 进行排序，同时修改数组 `index` 以反映排序过程中每个元素的位置变化。

这个程序的关键点在于，它不仅对输入的整数进行排序，还通过维护一个额外的 `index` 数组来跟踪排序过程中每个元素的位置变化。

#include <stdio.h>
// 升序
void bubble_sort(int arr[], int index[], int n) {
    int i, j, temp, temp_idx;
    for (i = 0; i < n - 1; i++) {
        for (j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                
                temp_idx = index[j];
                index[j] = index[j + 1];
                index[j + 1] = temp_idx;
            }
        }
    }
}

int main() {
    int arr[10];
    int index[10];
    int i;
    
    for (i = 0; i < 10; i++) {
        scanf("%d", &arr[i]);
        index[i] = i + 1;
    }

    // 冒泡
    bubble_sort(arr, index, 10);
    
    for (i = 0; i < 10; i++) {
        if(i==9)
            printf("%d",arr[i]);
        else
            printf("%d ", arr[i]);
    }
    printf("\n");

    // 遍历
    for (i = 0; i < 10; i++) {
        if(i==9)
            printf("%d",index[i]);
        else
            printf("%d ", index[i]);
    }
    
    return 0;
}