自然数数组的排序

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, x;
    cin>>n;
    int a[n+1];
    for(int i=0;i<n;i++){
        cin>>x;
        a[x] = x;
    }
    for(int i=1;i<=n;i++)
        cout<<a[i]<<" ";
    return 0;
}

import java.util.*;
public class Main{
    public static void main(String arg[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i=0;i<n;i++) {
            arr[i] = sc.nextInt();
        }
        for (int i=0;i<n;i++) {
            while (arr[i]!=arr[arr[i]-1]) {
                swap(arr, i, arr[i]-1);
            }
            System.out.print(arr[i]+" ");
        }
    }
    public static void swap(int[] arr, int i, int j) {
        if (i==j) return;
        arr[i] = arr[i]^arr[j];
        arr[j] = arr[i]^arr[j];
        arr[i] = arr[i]^arr[j];
    }
}

const N = Number(readline());
const arr = readline().split(' ').map(Number);
// 长度为N的数组，想要按顺序装入1~N的值
// 排好序后，每个位置上的值和其下标必定满足关系 arr[i] === i + 1;
// 所以遍历原始数组，当遇到不满足 arr[i] === i + 1 条件的，则说明 arr[i] 不应该
// 放在当前的位置 i 上，而是需要移动的，然后就开始移动操作。
let cache; // 缓存当前要移动的数值
let start; // 缓存本轮移动操作是从哪个下标位置开始的
for (let i = 0; i < N; i++) {
  if (arr[i] !== i + 1) {
    cache = arr[i]; // 用cache缓存当前要移动的值
    start = i; // start记录本轮移动开始时的下标位置
    let target = cache - 1; // cache值应该被放在的下标位置
    // 在不断移动的过程中，只要下一个target位置还没有等于本轮移动开始时的start位置，
    // 说明本轮移动过程还没有结束，因为在把各个值放入它应该在的位置的最后，必然会把应该在 start 位置
    // 的值给替换出来，所以当本应该在start位置的值被找到后，直接把它放入start位置，此时就没有还在数组之
    // 外的值，本轮替换才算结束。
    while (target !== start) {
      const tmp = arr[target]; // 替换出当前不应该在target位置的值
      arr[target] = cache; // 把当前要移动的值放在它本应在的target位置
      cache = tmp; // 被替换出的tmp成为下一个要移动的值
      target = cache - 1; // target 也更新为下一个要移动的值，也就是 tmp，本应在的位置
    }
    arr[start] = cache; // 循环结束时，cache中是本应在start位置的值
  }
}
console.log(arr.join(' '));

#include<iostream>
using namespace std;
const int N = 1e5+3;
int a[N];


int main() {
    int n;
    scanf("%d", &n);
    for(int i=1;i<=n;++i) scanf("%d", a+i);
    for(int i=1;i<=n;++i) {
        while(a[i]!=i) {
            swap(a[i], a[a[i]]);
        }
        
    }
    for(int i=1;i<=n;++i) {
        printf("%d ", a[i]);
    }
    
    
}

这TM有啥好说的？？？

/*
 * @Description: 自然数数组的排序
 * @Author: 
 * @Date: 2020-11-13 22:03:44
 * @LastEditTime: 2020-11-13 22:10:03
 * @LastEditors: Please set LastEditors
 */
#include<iostream>
#include<vector>
using namespace std;
int main(){

    int N;
    cin >> N;
    vector<int> arr(N + 1);
    int temp;//暂时存放数
    for(int i = 0;i < N;i++){
        cin >> temp;
        arr[temp] = temp;
    }
    for(int i = 1;i < arr.size();i++){
        cout << arr[i] << " ";
    }
    system("pause");
    return 0;
}

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

int main()
{
    int n,a;
    cin>>n;
    vector<int> arr;
    for(int i=0;i<n;i++)
    {
        cin>>a;
        arr.push_back(a);
    }
    int middle;
    int i=0;                //从0下标开始循环
    while(i<n)
    {
        if(arr[i]==i+1)    //若该数的位置正确，则循环下一个
        {
            i++;
        }
        else
        {
            middle=arr[arr[i]-1];    //若不正确，找到arr[i]数对应的正确位置，交换一下
            arr[arr[i]-1]=arr[i];
            arr[i]=middle;
        }
    }
    for(int i=0;i<n;i++)
    {
        cout<<arr[i];
        cout<<" ";
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin>>n;
    int tmp[n+1];
    for(int i=0;i<n;i++){
        int num;
        cin>>num;
        tmp[num]=num;
    }
    for(int i=1;i<n+1;i++)
        cout<<tmp[i]<<' ';
    return 0;
}

N = eval(input())
ls = list(map(int, input().split()))
ls.sort()
print(' '.join(map(str, ls)))

N = eval(input())
ls = list(map(int, input().split()))
for i in range(N):
    if ls[i] == i+1: # 若位置i上的值为i+1,则位置正确
        continue
    else: # 若位置i上的值不正确时
        i_index = ls.index(i+1) #先确定i+1 的正确位置
        # 将值为i+1的位置与位置i互换
        ls[i], ls[i_index] = ls[i_index], ls[i]
print(' '.join(map(str, ls)))