C++ 无 vector 排序交换次数：最少交换次数使数列升序

思路：

1. 遍历数列a，用一个map记录每个数字的下标。
2. 对数列a进行排序，得到有序数列b。
3. 遍历数列b，如果b[i]不等于a[i]，则找到b[i]在数列a中的下标j，并将a[i]与a[j]交换，交换次数加一。
4. 输出交换次数。

具体实现如下：

#include #include

int main() { int n; cin >> n;

int a[n];
map<int, int> index;

for (int i = 0; i < n; i++) {
    cin >> a[i];
    index[a[i]] = i;
}

int b[n];
for (int i = 0; i < n; i++) {
    b[i] = a[i];
}

sort(b, b + n);

int count = 0;
for (int i = 0; i < n; i++) {
    if (a[i] != b[i]) {
        int j = index[b[i]];
        swap(a[i], a[j]);
        index[a[i]] = i;
        index[a[j]] = j;
        count++;
    }
}

cout << count << endl;

return 0;

}