问题背景

小哼的学校要建立一个图书角，老师派小哼去找一些同学做调查，看看同学们都喜欢看那些书，小哼让每个同学写出一个自己最想读的书的ISBN号，去掉重复的ISBN号，然后从小到大排序后交给老师~~ 要求1秒完成啊~~

解决方案

先去重后排序

#include <stdio.h>

int main(int argc, const char * argv[]) {
    // insert code here...
    int n;
    int a[1001];
    scanf("%d", &n);    //要排序的个数
    for (int i=0; i<1001; i++) {  //
        a[i] = 0;
    }
    int k;
    for (int i=0; i<n; i++) {
        scanf("%d", &k);
        a[k] = 1;
    }
    
    for (int i=0; i<1001; i++) {
        if (a[i]==1) {
            printf("%d ", i);
        }
    }
    return 0;
}

先排序后去重

#include <stdio.h>
int n;
int a[1001];

int main(int argc, const char * argv[]) {
    // insert code here...
    scanf("%d", &n);
    for (int i=0; i<n; i++) {
        scanf("%d", &a[i]);
    }
    
    //排序，冒泡排序
    for (int i=0; i<n-1; i++) {
        for (int j=1; j<n-i; j++) {
            if (a[j-1]>a[j]) {
                int t = a[j-1];
                a[j-1] = a[j];
                a[j] = t;
            }
        }
    }
    
    //去重
    int k = -1;
    for (int i=0; i<n; i++) {
        if (k!=a[i]) {
            printf("%d ",a[i]);
        }
        k = a[i];
    }

    return 0;
}

分析

假如每个图书ISBN号都是1_{1000的整数，并且参加调查的同学数不超过100，计算机每秒大约运行10亿次，因此以上两中方法都能满足需求。如果图书ISBN号是在-2147483648}2147483647的话那么第一种方法就不可行了，因为无法申请出这么大的数组来标记每一个ISBN号。使用冒泡排序对10万个数进行排序，计算机需要执行100亿次，显然无法在1秒钟完成。所以这个可以将冒泡排序改为快速排序，100000 * lg(100000) ~ 170万次。可以完成的。

快速排序

#include <stdio.h>
int n;
int a[1001];

void quitSort(int left, int right) {
    
    if (left > right) {
        return;
    }
    
    
    int i=left;
    int j=right;
    
    int temp = a[left];
    while (i!=j) {
        while (a[j] >= temp && j > i) {
            j--;
        }
        
        while (a[i] <= temp && j > i) {
            i++;
        }
        
        if (j>i) {
            int t = a[j];
            a[j] = a[i];
            a[i] = t;
        }
    }
    
    a[left] = a[i];
    a[i] = temp;
    
    
    quitSort(left, i-1);
    quitSort(i+1, right);
    
    return;
    
}

int main(int argc, const char * argv[]) {
    // insert code here...
    scanf("%d", &n);
    
    for (int i=0; i<n; i++) {
        scanf("%d", &a[i]);
    }
    
    quitSort(0, n-1);
    
    //去重
    printf("%d ",a[0]);
    for (int i=1; i<n; i++) {
        if (a[i]!=a[i-1]) {
            printf("%d ", a[i]);
        }
    }
    
    printf("\n");
    return 0;
}