一个O(n)的排序

之前的博客写得有问题，且不好理解，现在给一个很好的例子，方便理解

这个时间复杂度O(n)的前提是存在n个数，且递增，知道第一个数及递增的多少

例举一个最简单的例子  初值1，每个数递增1

即a[0] = 1,

  a[1] = 2;  ……………………………………

 

  代码如下

 

for(int i = 0; i < n; )

{

     temp = a[a[i] -1];

     a[a[i] - 1] = a[i];

     a[i] = temp;

     if(a[i] == i + 1)

        i++;

}

 

本人认为该代码可行，对于有规律的数不失为一个好办法。

上面的是关键的代码，下面的是我的简单例子
panda@panda-pc:~/Code/c$ cat n_paixu.c
#include

int main(void)
{
    int i;
    int n = 10;
    int temp;
    int a[10] = {1,2,7,8,9,10,3,4,5,6};
    for( i = 0; i < n; )
    {
        temp = a[a[i] -1];
        a[a[i] - 1] = a[i];
        a[i] = temp;
        if(a[i] == i + 1)
           i++;
    }
    for(i = 0;i < n;i++)
    {
        printf("%d\t",a[i]);
    }
    printf("\n");
    return 0;
}
运行结果：
panda@panda-pc:~/Code/c$ ./n_paixu
1    2    3    4    5    6    7    8    9    10  

最后我有一个想法，既然都知道第一个数了，而且又知道数的个数了，可以直接赋值更简单啦…………