利用数组索引进行排序

看到一道算法面试题,比较有趣,我自己用C做了一下。

题目:随机生成10个100以内的整数,把数据从小到大排序,而且算法复杂度只能是1。

这个算法比较有意思的地方是,首先建立一个数组B,其元素个数为数组A的最大元素值,然后用A的元素作为B的数组下标,然后给存在的B元素赋值,这样就可以用循环把下标输出出来。

C程序如下:

  1. #include <stdio.h>  
  2. #include <stdlib.h>  
  3. #include <time.h>  
  4. #define random(x) (rand()%x)  
  5.   
  6. main()  
  7. {  
  8.     int lengthA, lengthB, i;  
  9.     int wait;  
  10.       
  11.     int arrayA[10]; // 定义一个数组  
  12.     int arrayB[101];  
  13.     srand(time(NULL)); // 让每次产生的随机数都不一样  
  14.   
  15.     lengthA = sizeof(arrayA) / sizeof(arrayA[0]);  
  16.     lengthB = sizeof(arrayB) / sizeof(arrayB[0]);  
  17.           
  18.     // 给数组赋值  
  19.     for(i = 0; i < 10; i++)  
  20.         arrayA[i] = random(100);  
  21.   
  22.     printf(“随机生成的数组A的元素为 \n”);  
  23.   
  24.     // 输出数组  
  25.     for(i = 0; i < 10; i++)  
  26.         printf(“%d\n”, arrayA[i]);  
  27.   
  28.     for (i = 0; i < lengthA; i++)  
  29.     {  
  30.         arrayB[arrayA[i]] = 101;  
  31.     }  
  32.   
  33.     printf(“排序后的结果为\n”);  
  34.   
  35.     for (i = 0; i < lengthB; i++)  
  36.     {  
  37.         if (arrayB[i] == 101)  
  38.             printf(“%d\n”, i);  
  39.     }  
  40.   
  41.     //printf(“%d”, lengthA);  
  42.     scanf(“%d”, &wait);  

 

程序运行结果:
随机生成的数组A的元素为
79
62
87
43
32
52
72
88
44
53
排序后的结果为
32
43
44
52
53
62
72
79
87
88

 

Leave a Reply

Your email address will not be published.