Ordenar una array que contiene de 1 a n valores

Ha dado una array que contiene de 1 a n elementos, su tarea es ordenar esta array de una manera eficiente y sin reemplazarla con 1 a n números.
Ejemplos: 
 

Input : arr[] = {10, 7, 9, 2, 8, 
                 3, 5, 4, 6, 1};
Output : 1 2 3 4 5 6 7 8 9 10

Enfoque nativo: 
ordene esta array con el uso de cualquier tipo de método de clasificación. tarda O (nlogn) tiempo mínimo.
Enfoque eficiente: 
reemplace cada elemento con su posición. toma O (n) tiempo eficiente y le da la array ordenada. Entendamos este enfoque con el siguiente código. 
 

// Efficient C++ program to sort an array of
// numbers in range from 1 to n.
#include <bits/stdc++.h>
 
using namespace std;
 
// function for sort array
void sortit(int arr[], int n)
{
    for (int i = 0; i < n; i++) {
      arr[i]=i+1;
    }
}
 
// Driver code
int main()
{
    int arr[] = { 10, 7, 9, 2, 8, 3, 5, 4, 6, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // for sort an array
    sortit(arr, n);
 
    // for print all the element in sorted way
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";   
}

// Efficient Java program to sort an
// array of numbers in range from 1
// to n.
import java.io.*;
import java.util.*;
 
public class GFG {
     
         
    // function for sort array
    static void sortit(int []arr, int n)
    {
        for (int i = 0; i < n; i++)
        {
            arr[i]=i+1;
     
             
        }
    }
     
    // Driver code
    public static void main(String args[])
    {
        int []arr = {10, 7, 9, 2, 8,
                            3, 5, 4, 6, 1};
        int n = arr.length;
     
        // for sort an array
        sortit(arr, n);
     
        // for print all the
        // element in sorted way
        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
    }
}
 
// This code is contributed by Manish Shaw
// (manishshaw1)

# Python3 program to sort an array of
# numbers in range from 1 to n.
 
# function for sort array
def sortit(arr,n):
    for i in range(n):
        arr[i] = i+1
 
# Driver code
if __name__=='__main__':
    arr = [10, 7, 9, 2, 8, 3, 5, 4, 6, 1 ]
    n = len(arr)
 
    # for sort an array
    sortit(arr,n)
 
    # for print all the element
    # in sorted way
    for i in range(n):
        print(arr[i],end=" ")
  
# This code is contributed by
# Shrikant13

// Efficient C# program to sort an array of
// numbers in range from 1 to n.
using System;
using System.Collections.Generic;
 
class GFG {
     
         
    // function for sort array
    static void sortit(int []arr, int n)
    {
        for (int i = 0; i < n; i++)
        {
     
            arr[i]=i+1;
        }
    }
     
    // Driver code
    public static void Main()
    {
        int []arr = {10, 7, 9, 2, 8,
                      3, 5, 4, 6, 1};
        int n = arr.Length;
     
        // for sort an array
        sortit(arr, n);
     
        // for print all the
        // element in sorted way
        for (int i = 0; i < n; i++)
            Console.Write(arr[i] + " ");
    }
}
 
// This code is contributed by
// Manish Shaw (manishshaw1)

<?php
// Efficient PHP program to sort an
// array of numbers in range from 1 to n.
 
 
// function for sort array
function sortit(&$arr, $n)
{
    for ($i = 0; $i < $n; $i++)
    {
 
        $arr[$i]=$i+1; 
    }
}
 
// Driver code
$arr = array(10, 7, 9, 2, 8,
             3, 5, 4, 6, 1);
$n = count($arr);
 
// for sort an array
sortit($arr, $n);
 
// for print all the
// element in sorted way
for ($i = 0; $i < $n; $i++)
    echo $arr[$i]." ";
 
//This code is contributed by Manish Shaw
//(manishshaw1)
?>

<script>
 
// Efficient JavaScript program to sort an array of
// numbers in range from 1 to n.
 
// function for sort array
function sortit(arr, n)
{
    for (let i = 0; i < n; i++) {
    arr[i]=i+1;
    }
}
 
// Driver code
 
    let arr = [ 10, 7, 9, 2, 8, 3, 5, 4, 6, 1 ];
    let n = arr.length;
 
    // for sort an array
    sortit(arr, n);
 
    // for print all the element in sorted way
    for (let i = 0; i < n; i++)
        document.write(arr[i] + " ");    
 
 
// This code is contributed by Surbhi Tyagi.
 
</script>

1 2 3 4 5 6 7 8 9 10

Complejidad de tiempo: O(n)

Complejidad espacial: O(1)