关于一道1到N自然数排序的华为面试题的疑问,该如何解决

关于一道1到N自然数排序的华为面试题的疑问
首先声明，小弟才疏学浅，java水平不高。
看到网上有关这道排序题，有点疑问。具体题目如下：
有N个大小不等的自然数（1--N），请将它们由小到大排序。  
要求程序算法：时间复杂度为O(n)，空间复杂度为O(1)。

看到网上有好多高手解答，例如：

int cnt = 0;//辅助变量，不是算法组成部分

void sort(int arr[], int n){

 int t; /**//*临时变量：空间复杂度O(1)*/ 

 //可以证明这个算法每次交换必然将一个数字正确安排到位，而且最多只有N次交换。 

 //具体体现在cnt的值上，所以虽然是二重循环仍然是时间复杂度O(n)

 for (int i = 1; i <= n; i++){

  while(arr[i] != i){

  t = arr[arr[i]];

  arr[arr[i]] = arr[i];

  arr[i] = t;

  ++cnt;

  }

 }

}

小弟有个疑问，就是具体体现在cnt的值上，这指的到底是啥意思？如果没有这个值的话这个的算法复杂度就不是n了？有这个值怎么是n的？

小弟的实现：
//据说时间复杂度是o(n)的算法
public class OnSort {
public static void main(String[] args) {
int[] array = new int[] { 7, 6, 5, 4, 3, 2, 1 };
sort(array);
}

public static void temp(int[] arr) {
int temp;
for (int i = 0; i < arr.length; i++) {
while (arr[i] != i + 1) {
temp = arr[i];
arr[i] = arr[arr[i] - 1];
arr[temp - 1] = temp;
}
}
}

public static void sort(int[] arr) {
temp(arr);
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
}
这个的复杂度和上面贴出来的有什么区别呢？
希望大虾们不吝赐教

[解决办法]
cnt就是起到一个计数的作用，计算交换了多少次，完全可以不要
[解决办法]

Java code

import java.util.Arrays;import java.util.Random;/** * 有N个大小不等的自然数（1--N），请将它们由小到大排序。 要求程序算法：时间复杂度为O(n)，空间复杂度为O(1)。 *  * @author chouy */public class SortArrayFrom1toN extends Base{    public static int N = 5000;    public static Random random = new Random();    public static void main(String[] args)    {        int[] is = new int[N];        for (int i = 0; i < is.length; i++)        {            is[i] = i;        }        // 打乱顺序        int tmp;        for (int i = 0; i < is.length; i++)        {            int j = random.nextInt(N);            tmp = is[i];            is[i] = is[j];            is[j] = tmp;        }        info(Arrays.toString(is));        info(Arrays.toString(new SortArrayFrom1toN().sort(is)));    }    /**     * 用交换的方法进行排序.<br>     * 交换方法:交换回来的数如果不应该在当前位置,则再把它与它应该在的位置交换     *      * @param array     * @return     */    public int[] sort(int[] array)    {        int exchangeTimes = 0; // 比较计数器        int tmp;        for (int i = 0; i < array.length; i++)        {            if (array[i] != i)            {                tmp = array[array[i]];                array[array[i]] = array[i];                array[i] = tmp;                i--;                exchangeTimes++;            }        }        debug("exchangeTimes = " + exchangeTimes);        return array;    }}
------解决方案-------------------- 
 
这样才有点意义吧，否则用得着排序吗？
C# code
        private interface ISort { public int sort { get; } }        private static void sort<valueType>(valueType[] values) where valueType : ISort        {            valueType value, nextValue;            for (int nextIndex, index = values.Length - 1; index > 0; index--)            {                if ((nextIndex = (value = values[index]).sort - 1) != index)                {                    do                    {                        nextValue = values[nextIndex];                        values[nextIndex] = value;                    }                    while ((nextIndex = (value = nextValue).sort - 1) != index);                    values[index] = value;                }            }        }
[解决办法]
探讨

n就是让你统计执行次数，没换一次就少执行一次了，时间是O(n)

[解决办法]
个人认为cnt只是计数，用来证明时间复杂度为O(n)
[解决办法]
这个方法很到位，“有N个大小不等的自然数（1--N）”这个条件给的很舒服的，一般没那么简单的。
[解决办法]
C/C++ code
int a[] = { 3,6,7,1,2,4,5};void sort(int arr[]){    int idx = 0;    int i = 0;    while(true)    {        if(a[i] == a[a[i] - 1])            i ++ ;        if(i > 6)            break;        idx = a[a[i] - 1] ;        a[a[i] - 1 ] = a[i];        a[i] = idx;     }}int _tmain(int argc, _TCHAR* argv[]){    sort(a);    return 0;}