数据结构与算法学习（day4）——解决实际问题

前言

1. 在本章的学习此前，需要复习前三章的内容，每个算法都动手敲一遍解题。宁愿学慢一点，也要对每个算法掌握基本的理解！

2. 前面我们学习了简化版桶排序、冒泡排序和快速排序三种算法，今天我们来实践一下前面的三种算法。

3. 本章的学习目标：

（1）回顾三个算法的基本原理，能够熟悉运用三个算法解决问题

（2）用三种不同算法解决同一个问题

题目

（1）输入有2行，第1行为一个正整数，表示有n个同学参与调查（n<=100）。第2行有n个用空格隔开的正整数，为每本图书的ISBN号（假设图书的ISBN号在1~1000）。

（2）输出也是2行。第1行为一个正整数k，表示需要买多少本书。第2行为k个用空格隔开的正整数，为从小到大已排好序的需要购买的图书的ISBN号（去重）。

例如输入：

10
20 40 32 67 40 20 89 300 400 15
1
2

则输出：

8
15 20 32 40 67 89 300 400
1
2

（3）最后，程序运行的时间限制为1s。

分析题目

我们要实现的要求有：

1. 对数据按从小到大顺序排列
2. 去重

方法一

我想到的第一个方法就是用简化版桶排序。

程序如下：

#include 
int book[1001], n;
int main()
{
	int i, j, k=0, t;
	for (i = 0; i <= 1000; i++)
		book[i] = 0;
		
	scanf("%d",&n);
	for (i = 1; i <= n; i++)
	{
		scanf("%d", &t);
		book[t]++;

		if (book[t] == 1)
		{
			book[t] = 2;
			k++;
		}
		else if (book[t] > 2)
		{
			book[t] = 2;
		}
	}
	printf("%d\n",k);
	for (i = 1; i <= 1000; i++)
		if(book[i]==2)
			printf("%d ", i);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

效果如图

我们来评价一下这个程序，毫无疑问，这个程序比较无脑，不是一个巧妙的处理方式，但是也可以实现题目要求。

1. 程序运用的方法是比较简单的桶排序
2. 思路是先排序（排序实际上数组已经排好了），后去重。
3. 这个方法的时间复杂度就是桶排序的时间复杂度O(N+M)。

方法二

第二种方法也是先排序后去重，排序我们可以使用冒泡排序或者快速排序,这里我们用冒泡排序举例。

#include 
int main()
{
	int a[1001], i,j, n,t,k = 0;
	scanf("%d",&n);

	for (i = 0; i < n; i++)
		scanf("%d",&a[i]);

	//开始冒泡排序
	for (i = 0; i < n - 1; i++)
	{
		for (j = 0; j < n - i - 1; j++)
		{
			if (a[j] > a[j + 1])  //按从小到大的顺序排列
			{
				t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
			}
		}
	}

	for (i = 0; i < n; i++)
	{
		if (a[i] == a[i - 1])  //计算重复元素的个数
			k++;
	}

	printf("%d\n",n - k);

	for (i = 0; i < n; i++)
	{
		if(a[i] != a[i-1])
			printf("%d ", a[i]);
	}	
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

我们来评价一下这个程序，

1. 程序运用的方法是比较简单的冒泡排序
2. 思路是先排序，后去重。
3. 这个方法的时间复杂度就是桶排序的时间复杂度O(N^2)，冒泡排序的时间复杂度在整个程序中是大块，所以其他两个的时间复杂度不计，时间复杂度比较高。
4. 如果要排序的数字数量增大，大到10万，桶排序要申请更大的数组，不现实，而冒泡排序的时间复杂度高所以耗时不少，这时候就只能用快速排序，如下；

#include 
/*****************
*a[101]用于存放要排序的数组
* n是要排序的个数
*****************/
int a[1001], n;   //全局变量，这两个变量需要在子函数中使用
/*****************
* 函数名：quicksort
* 形参：int left, int right
* 返回值：无
* 作用：快速排序算法
* ****/
void quicksort(int left, int right)  // left一直都是1
{
	int i, j, t, temp;
	if (left > right)
		return;

	temp = a[left];  //temp中存的就是基准数
	i = left;
	j = right;
	while (i != j)  //相遇后跳出循环
	{
		//顺序很重要，要先从右往左找
		while (a[j] >= temp && i < j)
			j--;

		//再从左往右找
		while (a[i] <= temp && i < j)
			i++;

		//交换两个数再数组中的位置
		if (i < j)   //当哨兵i和哨兵j没有相遇时
		{
			t = a[i];
			a[i] = a[j];
			a[j] = t;
		}
	}

	//最终将基准数归位
	//若相遇，一定是在一个小于基准数的数相遇，将相遇时的数作为基准数进行下一轮的“探测”
	a[left] = a[i];
	a[i] = temp;

	quicksort(left,i-1);  //继续处理左边的，这里是一个递归的过程
	quicksort(i + 1, right);  //继续处理右边的，这里是一个递归的过程
}
int main()
{
	int i,j,k = 0;
	scanf("%d", &n);

	for (i = 1; i <= n; i++)
		scanf("%d", &a[i]);

	//开始快速排序
	quicksort(1, n);  //快速排序调用

	for (i = 1; i <= n; i++)
	{
		if (a[i] == a[i - 1])  //计算重复元素的个数
			k++;
	}

	printf("%d\n", n - k);

	for (i = 1; i <= n; i++)
	{
		if (a[i] != a[i - 1])
			printf("%d ", a[i]);
	}

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

（1）我们在写程序的时候，只要不是面试等需要现场手打程序，那我们可以利用之前写好的代码，移植到我们现在的问题上，来解决问题。

（2）所以，平时多储备知识和源码，还是很重要的，平时的积累，要求我们要掌握好知识，否则到移植的时候，半天都移植不成功。

小结

我们来回顾一下三个算法的时间复杂度。

（1）桶排序是最快的，时间复杂度为O(N+M);

（2）冒泡排序是O(N^2)

（3）快速排序是O(NlogN)

下一节，我们将进入栈、队列、链表的学习。