这几天看MFC，头晕眼花，也觉得没有什么可以写的。
今天学习之余，看到一个面试题“1000个范围0－2000的数字，进行排序打印出来”。就想着实现一下。
第一步先要建立1000个范围确定的不重复随机数字数组。
建立数组的过程，首先想到在循环中随机数对范围取模，新生成的数字再与之前已经生成的数字进行比较，如果不重复，则放入数组，与已有数字重复，则重复操作。这样实现出来之后，效率非常低下，不能接受。
既然范围确定，可以先建立一个顺序数组作为待选数组，然后从其中不断挑选数字。挑选数字时，以随机数为下标。这样做因为随机数会出现重复，挑选出的数字也就会重复。
解决随机数字重复的问题比较困难，可以使同样的下标，在不同轮数的数字不同。这就需要将已经选入数组的元素从待选数组中剔除。对于数组的操作，删除一个元素，将后续元素前移，效率有些低。可以将末尾的元素放到挑选出数字的位置，将待选数组的“长度”减一。如果选中的数字在数组的“尾部”，自赋值并不会出现问题，数组“长度”减一之后，刚刚挑选的元素也从待选数组中排除，所以尾部并不需要特殊处理。
用这种方法实现的随机数组，时间复杂度为O(n)，是比较理想的。
对于“排序”，根据要求只是“打印”，并且说明速度非常快。
这样同样需要多一个数组，称为标记数组
一遍遍历，将标记数组中随机数组元素对应的下标的元素标记。再一遍遍历，打印标记数组中有标记的“下标”。
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <time.h> 4 //生成无重复数字的随机数数组 5 void random_arr(int def_arr[], const int value, 6 int sel_arr[], const int size) 7 { 8 int i = 0; 9 //待选数组初始化 10 for (i = 0; i < value; i++) 11 def_arr[i] = i; 12 //从待选数组挑取数字到随机数组 13 i = 0; 14 int max = value; 15 while (i < size) 16 { 17 int temp = rand() % max; 18 sel_arr[i++] = def_arr[temp]; 19 def_arr[temp] = def_arr[--max]; 20 } 21 } 22 //打印数组 23 void print_arr(const int* arr, const int size) 24 { 25 int i = 0; 26 for (i = 0; i < size; i++) 27 printf("%d ", arr[i]); 28 printf(" "); 29 } 30 //主函数 31 int main(void) 32 { 33 srand(time(0)); 34 int size = 1000, value = 2000; 35 int def_arr[value]; 36 int sel_arr[size]; 37 random_arr(def_arr, value, sel_arr, size); 38 print_arr(sel_arr, size); 39 printf(" "); 40 //伪排序 41 int signal_arr[2000] = {0}; 42 int i = 0; 43 for (i = 0; i < 1000; i++) 44 signal_arr[sel_arr[i]] = 1; 45 for (i = 0; i < 2000; i++) 46 if (signal_arr[i] = 1) 47 printf("%d ", i); 48 printf(" "); 49 return 0; 50 }