排序总结之华为排序（三）

这次的排序我也不清楚具体名字是什么，是在网上搜到的华为的一个笔试题，姑且就称为华为排序吧。

原题如下：

有1,2,....一直到n的无序数组,求排序算法,并且要求时间复杂度为O(n),空间复杂度O(1),使用交换,而且一次只能交换两个数.（华为）

思路如下：

因为这个数组是从1开始的，而且也是连续的数，那么num[i]的值肯定是i+1。

那么就好办了，从第一个数开始循环，一个个放在正确的位置，把第i个数放在他正确的位置，即num[num[i] -1]；方法就是通过第i个数与在第(num[i]-1)个数替换。

具体实现代码如下：

#include

int main(int argc, char *argv[])
{
    int num[] = {8, 2, 4, 5, 1, 9, 10, 3, 7, 6};
    int n;
    int i;
    int temp;
   
    n = sizeof(num) / sizeof(int);
   
    for (i = 0; i < n;)   //排序
    {
        temp = num[num[i] - 1];
        num[num[i] - 1] = num[i];
        num[i] = temp;
   
        if ( num[i] == i + 1)
            i++;
    }
   
    for (i = 0; i < n; i++)
    {
        printf ("%d ", num[i]);
    }
    printf ("\n");
   
    return 0;
}