明明的随机数

思路

核心思想就是去重和排序
就看去重和排序怎么进行了，哪个在前，哪个在后。

1

简单排序，排序过程中去重 ——————未验证
可以用插入排序，有重复值的时候continue，进行下一个数据的排序。
用折半插入感觉更爽点。哈哈。
其他的冒泡选择什么之类的也可以啦，但是插入最对这个题的胃口的了。读一个数，插入一个，免得重新遍历一遍。

int insert_sort(int a[], int n)
{
    int i, j, low, high, mid, temp;
    for (i = 0; i < n; i++) {
        scanf("%d", &a[i]);

        temp = a[i];
        low = 0;
        high = i - 1;
        mid = (high + low) / 2;

        while(low < high) {
            if (temp = a[mid]) {
                break;
            } else if (temp < a[mid]) {
                high = mid -1;
            } else {
                low = mid + 1;
            }

        for (j = i; j > high + 1; j--) {
            a[j] = a[j - 1];
        }
        a[j] = temp;
        } 
    }

    return 0;
}

2

桶排序
a.用1000个桶来统计每个数据的出项次数，输出的时候进行去重。(直接桶排序)
b.用多个桶，每个桶进行插入排序，排序过程中进行去重。(常规桶排序)

a.直接桶排序代码: ——————验证ac

#include<stdio.h>
#include<string.h>

int hash[1001];

int main()
{
    int n = 0, i = 0, num = 0;

    while(scanf("%d", &n) != EOF) {
        memset(hash, 0, sizeof(hash));
        for(i = 0; i < n; i++) {
            scanf("%d", &num);
            hash[num]++;
        }

        for (i = 1; i < 1001; i++) {
            if (hash[i])
                printf("%d\n", i);
        }
    }

    return 0;
}

b.桶排序加插入排序。 ——————未验证
四个桶来搞吧，个位，十位，百位，千位。怎么有点像基数排序了。得用链表啊。
typedef struct _bucketNum{
int num;
_bucketNum *next;
}bucketNum；
int bucket_sort(int a[], int numLen, int bucketLen)
{
int i, temp, bucket;

bucketNum **bucketPoint = (bucketNum **)malloc(bucketLen * sizeof(bucketNum *));
if (!bucketPoint) {
    return -1;
}

for (i = 0; i < bucketLen; i++) {
    bucketPoint[i] = (bucketNum *)malloc(sizeof(bucketNum));
    if (!bucketPoint[i]) {
        while(--i) free(bucketPoint[i]);
        free(bucketPoint);
        return -1;
    }

    bucketPoint[i]->num = 0;
    bucketPoint[i]->next = null;
}

for (i = 0; i < numLen; i++) {
    scanf("%d", &temp);

    bucketNum *numNode = (bucketNum *) malloc(sizeof(bucketNum));
    numNode->num = temp;
    numNode->next = null;

    bucket = getBucketNum(numNode->num);//getBucketNum获取位数，就不实现了吧，挺简单的。
    bucketPointTemp = bucketPoint[bucket];
    if (!bucketPointTemp ->next]) {
        bucketPointTemp ->next = numNode;
        bucketPoint[bucket]->num++;
    } else {
        while(!bucketPointTemp->next) {
            if (bucketPointTemp->next->num == numNode->num) {
                free(numNode);
                break;
            } else (bucketPointTemp->next->num > numNode->num) {
                numNode->next = bucketPointTemp->next;
                bucketPointTemp>next = numNode;
                bucketPoint[bucket]->num++;
            }
            bucketPointTemp = bucketPointTemp->next;
        }
    }

    for (i = 0; i < bucketLen ; i++) {
         bucketPointTemp = bucketPointTemp[i];
        while (!bucketPointTemp->next) {
            printf("%d\n", bucketPointTemp->next->num);
            bucketPointTemp = bucketPointTemp->next;
            bucketPoint[bucket]--;
        }
    }

freeBucket(bucketPoint);//用完后要全部释放。实现这里就不写了。。。

return 0;

}

```
eg:
直接桶排序最简单，插入排序然后去重其次，常规桶排序最长了。
b的桶排序这个并不是针对N<=1000的情况写的。
思考了下这题的变体，如果N比较小，比如说100，并且数据集中分块(10附近一堆，100附近一堆，300一堆这种)，用直接桶排序，就是特别合适了。用几个桶就比较合适了，每个桶N个，空间比1000肯定小很多。

其实就是空间和时间的平衡，在平衡中找到最优方式。
直接映射肯定是最方便的，但是空间消耗是最大的；所以需要更改映射方案，但是代价就是增加了一部分的时间开销。