💐The Begin💐点点关注，收藏不迷路💐

输入n个不相同的正整数，每个数都不超过n。现在需要你把这些整数进行升序排序，每次可以交换两个数的位置，最少需要多少次操作才可以完成排序。

输入

第一行输入n（1≤n≤105）

第二行为n个互不相等且不大于n的正整数。

输出

输出最少交换次数。

样例输入

3
3 2 1

样例输出

1

提示
样例解释：交换3和1

通过遍历数组，检查每个位置上的数是否处于其应该在的位置（按照从小到大排序的正确位置），如果不是，则找到应该在当前位置的那个数的下标，然后交换这两个数的位置，每进行一次这样的交换操作，记录交换次数的变量就加1，最后输出总的交换次数。

C语言实现

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

#define MAX_N 100005
int n;
int arr[MAX_N];  // 存储输入的整数数组

// 找到数组中值为x的元素的下标
int findIndex(int x) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == x) {
            return i;
        }
    }
    return -1;  // 正常情况下不会执行到这，只是为了符合函数返回值类型添加
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    int count = 0;  // 记录交换次数
    for (int i = 0; i < n; i++) {
        if (arr[i]!= i + 1) {  // 如果当前位置的数不等于其应该在的位置（从小到大排序时的位置）
            int index = findIndex(i + 1);  // 找到应该在当前位置的数的下标
            int temp = arr[i];
            arr[i] = arr[index];
            arr[index] = temp;  // 交换两个数的位置
            count++;
        }
    }
    printf("%d\n", count);
    return 0;
}

C++实现

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);  // 使用vector存储输入的整数数组
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    int count = 0;  // 记录交换次数
    for (int i = 0; i < n; i++) {
        if (arr[i]!= i + 1) {  // 如果当前位置的数不等于其应该在的位置（从小到大排序时的位置）
            int index = 0;
            for (int j = 0; j < n; j++) {
                if (arr[j] == i + 1) {
                    index = j;
                    break;
                }
            }
            swap(arr[i], arr[index]);  // 交换两个数的位置
            count++;
        }
    }
    cout << count << endl;
    return 0;
}

Java实现

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }
        int count = 0;  // 记录交换次数
        for (int i = 0; i < n; i++) {
            if (arr[i]!= i + 1) {  // 如果当前位置的数不等于其应该在的位置（从小到大排序时的位置）
                int index = 0;
                for (int j = 0; j < n; j++) {
                    if (arr[j] == i + 1) {
                        index = j;
                        break;
                    }
                }
                int temp = arr[i];
                arr[i] = arr[index];
                arr[index] = temp;  // 交换两个数的位置
                count++;
            }
        }
        System.out.println(count);
    }
}

Python实现

n = int(input())
arr = list(map(int, input().split()))
count = 0
for i in range(n):
    if arr[i]!= i + 1:  # 如果当前位置的数不等于其应该在的位置（从小到大排序时的位置）
        index = arr.index(i + 1)  # 找到应该在当前位置的数的下标
        arr[i], arr[index] = arr[index], arr[i]  # 交换两个数的位置
        count += 1
print(count)

💐The End💐点点关注，收藏不迷路💐