【蓝桥杯】【啊哈！算法】小哼买书 —— 排序算法的应用

左手的ㄟ右手 2022-11-16 01:46 183阅读 0赞

## [【啊哈！算法】系列文章目录][Link 1] ##

--------------------

### 目录 ###

*   *  【啊哈！算法】系列文章目录
     *   *  需求介绍
         *  思路分析
         *  C语言代码
         *   *  方法一
             *  方法二

--------------------

### 需求介绍 ###

小哼的学校要建立一个图书角，老师派小哼去找一些同学做调查，看看同学们都喜欢读哪些书。小哼让每个同学写出一个自己最想读的书的 ISBN 号（你知道吗？每本书都有唯一的 ISBN 号，不信的话你去找本书翻到背面看看）。当然有一些好书会有很多同学都喜欢，这样就会收集到很多重复的 ISBN 号。小哼需要去掉其中重复的 ISBN 号，即每个 ISBN 号只保留一个，也就说同样的书只买一本（学校真是够抠门的）。然后再把这些 ISBN 号从小到大排序，小哼将按照排序好的 ISBN 号去书店买书。请你协助小哼完成“去重”与“排序”的工作。  
  输入有 2 行，第 1 行为一个正整数，表示有 n 个同学参与调查（n≤100）。第 2 行有 n 个用空格隔开的正整数，为每本图书的 ISBN 号（假设图书的 ISBN 号在 1~1000 之间）。  
  输出也是 2 行，第 1 行为一个正整数 k，表示需要买多少本书。第 2 行为 k 个用空格隔开的正整数，为从小到大已排好序的需要购买的图书的 ISBN 号。  
  例如输入：

10 
    	20 40 32 67 40 20 89 300 400 15

则输出：

8 
    	15 20 32 40 67 89 300 400

最后，程序运行的时间限制为 1 秒。

### 思路分析 ###

解决这个问题的方法大致有两种。  
  **第一种方法：** 先将这 n 个图书的 ISBN 号去重，再进行从小到大排序并输出；  
  **第二种方法：** 先从小到大排序，输出的时候再去重。

### C语言代码 ###

#### 方法一 ####

**桶排序+筛选**

// 桶排序+筛选
    /* 说明： 若每个图书ISBN 号都是1~1000 之间的整数，图书数量 n 的范围不是小于等于100，而是小 于等于10 万 时 适用此法。 */ 
    
    # include <stdio.h>
    
    int main() { 
    	int book[1001],i,k,n;
    	scanf("%d",&n);
    	for(i=0;i<=1000;i++) { 
    		book[i] = 0;
    	}
    	for(i=0;i<n;i++) { 
    		scanf("%d",&k);
    		book[k]++;
    	} 
    	for(i=0;i<=1000;i++) { 
    		if(book[i]>0) { 
    			printf("%d ",i);
    		}
    	}	
    	return 0;
    }
    
    /* 输入： 10 20 40 32 67 40 20 89 300 400 15 输出： 15 20 32 40 67 89 300 400 */

这种方法的时间复杂度就是桶排序的时间复杂度，为 O(N+M)。

#### 方法二 ####

**快速排序+筛选**

// 快速排序+筛选
    
    # include <stdio.h>
    
    long long a[100000];
    
    void quicksort(long long left, long long right) { 
    	long long i,j,k,temp;
    	if(left>right) { 
    		return; 
    	}
    	temp = a[left];
    	i = left;
    	j = right;
    	while(i!=j) { 
    		while(a[j]>=temp && i<j) { 
    			j--;
    		}
    		while(a[i]<=temp && i<j) { 
    			i++;
    		}
    		if(i<j){ 
    			k = a[j];
    			a[j] = a[i];
    			a[i] = k;
    		}
    	}
    	a[left] = a[i];
    	a[i] = temp;
    	
    	quicksort(left,i-1);
    	quicksort(i+1,right);
    }
    
    int main() { 
    	long long i,n;
    	scanf("%lld",&n);
    	for(i=0;i<n;i++) { 
    		scanf("%lld",&a[i]);
    	}
    	quicksort(0,n-1);
    	printf("%lld ",a[0]);
    	for(i=1;i<n;i++) { 
    		if(a[i]!=a[i-1]) { 
    			printf("%lld ",a[i]);
    		}
    	}
    	return 0;
    }
    
    
    /* 输入： 10 20 40 32 67 40 20 89 300 400 15 输出： 15 20 32 40 67 89 300 400 */

这种方法的时间复杂度由两部分组成，一部分是冒泡排序的时间复杂度，是  N ( N 2 ) N (N^2) N(N2)，另一部分是读入和输出，都是  O ( N ) O(N) O(N)，因此整个算法的时间复杂度是  O ( 2 ∗ N + N 2 ) O(2\*N+N^2) O(2∗N\+N2)。相对于  N 2 N^2 N2来说， 2 ∗ N 2\*N 2∗N 可以忽略（我们通常忽略低阶），最终该方法的时间复杂度是  O ( N 2 ) O(N^2) O(N2)。

[Link 1]: https://blog.csdn.net/weixin_43964993/article/details/115446128