太原本地网站搭建公司,现代风格装修效果图,企业建站系统漏洞,不用下载就能玩的网页游戏前言 在本章的学习此前#xff0c;需要复习前三章的内容#xff0c;每个算法都动手敲一遍解题。宁愿学慢一点#xff0c;也要对每个算法掌握基本的理解#xff01; 前面我们学习了简化版桶排序、冒泡排序和快速排序三种算法#xff0c;今天我们来实践一下前面的三种算法。…前言 在本章的学习此前需要复习前三章的内容每个算法都动手敲一遍解题。宁愿学慢一点也要对每个算法掌握基本的理解 前面我们学习了简化版桶排序、冒泡排序和快速排序三种算法今天我们来实践一下前面的三种算法。 本章的学习目标 1回顾三个算法的基本原理能够熟悉运用三个算法解决问题 2用三种不同算法解决同一个问题 题目 1输入有2行第1行为一个正整数表示有n个同学参与调查n100。第2行有n个用空格隔开的正整数为每本图书的ISBN号假设图书的ISBN号在1~1000。 2输出也是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 4003最后程序运行的时间限制为1s。 分析题目 我们要实现的要求有 对数据按从小到大顺序排列去重 方法一
我想到的第一个方法就是用简化版桶排序。
程序如下
#include stdio.h
int book[1001], n;
int main()
{int i, j, k0, 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);
}效果如图 我们来评价一下这个程序毫无疑问这个程序比较无脑不是一个巧妙的处理方式但是也可以实现题目要求。 程序运用的方法是比较简单的桶排序思路是先排序排序实际上数组已经排好了后去重。这个方法的时间复杂度就是桶排序的时间复杂度O(NM)。 方法二
第二种方法也是先排序后去重排序我们可以使用冒泡排序或者快速排序,这里我们用冒泡排序举例。
#include stdio.h
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;
} 我们来评价一下这个程序 程序运用的方法是比较简单的冒泡排序思路是先排序后去重。这个方法的时间复杂度就是桶排序的时间复杂度O(N^2)冒泡排序的时间复杂度在整个程序中是大块所以其他两个的时间复杂度不计时间复杂度比较高。如果要排序的数字数量增大大到10万桶排序要申请更大的数组不现实而冒泡排序的时间复杂度高所以耗时不少这时候就只能用快速排序如下 #include stdio.h
/*****************
*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所以平时多储备知识和源码还是很重要的平时的积累要求我们要掌握好知识否则到移植的时候半天都移植不成功。 小结 我们来回顾一下三个算法的时间复杂度。 1桶排序是最快的时间复杂度为O(NM); 2冒泡排序是O(N^2) 3快速排序是O(NlogN) 下一节我们将进入栈、队列、链表的学习。
