Java教程

第一次练习总结

本文主要是介绍第一次练习总结,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

本周的测试主要针对排序算法进行练习。

1、冒泡排序:

1)比较相邻的元素。如果第一个比第二个大,就交换他们两个。
2)每趟从第一对相邻元素开始,对每一对相邻元素作同样的工作,直到最后一对。
3)针对所有的元素重复以上的步骤,除了已排序过的元素(每趟排序后的最后一个元素),直到没有任何一对数字需要比较。

例:

(图源网络)

冒泡排序的原理:
每一趟只能确定将一个数归位。即第一趟只能确定将末位上的数归位,第二趟只能将倒数第 2 位上的数归位,依次类推下去。如果有 n 个数进行排序,只需将 n-1 个数归位,也就是要进行 n-1 趟操作。而 “每一趟 ” 都需要从第一位开始进行相邻的两个数的比较,将较大的数放后面,比较完毕之后向后挪一位继续比较下面两个相邻的两个数大小关系,重复此步骤,直到最后一个还没归位的数。

代码:

void bubbleSort(int a[], int n)
{
    for(int i = n - 1; i > 0; i--)
        for(int j = 0; j < i; j++)
            if(a[j] > a[j+1]) 
                swap(a[j], a[j+1]);
}

冒泡排序是一种稳定的排序,在冒泡排序中,遇到相等的值,是不进行交换的,只有遇到不相等的值才进行交换,所以是稳定的排序方式。

2、sort();函数排序:

sort();是一种类似于快速排序的方法,时间复杂度为n*log2(n),执行效率较高,在C++中使用sort()函数需要使用#include <algorithm>头文件。

sort()函数可以对给定区间所有元素进行排序。它有三个参数sort(begin, end, cmp),其中begin为指向待sort()的数组的第一个元素的指针,end为指向待sort()的数组的最后一个元素的下一个位置的指针,cmp参数为排序准则,cmp参数可以不写,如果不写的话,默认从小到大进行排序。

如若按照每个数的个位进行从大到小排序,我们就可以根据自己的需求来写一个函数作为排序的准则传入到sort()中。

例:

int cmp(string a,string b)
{
	string a1 = a.substr(6,8);
	string b1 = b.substr(6,8);
	if(a1 == b1)
	{
		return a > b;
	}
	else 
	{
		return a1 > b1;
	}
} 

然后我们将这个cmp函数作为参数传入sort()中即可实现了上述排序需求。substr();函数,用于复制子字符串,要求从指定位置开始,并具有指定的长度。其中的substr(6,8);表示从下标为6开始截取长度为8位。

3、拓扑排序:

在AOV网中不能出现回路。设G=(V,E)是一个有向图,V中的顶点序列v_{0 },v_{1},...,v_{n-1}称为一个拓扑排序,当且仅当满足下列条件:若从顶点v_{i}v_{j}有一条路径,则在顶点序列中顶点v_{i}必在v_{j}之前。对一个有向图构造拓扑序列的过程称为拓扑排序。

 

 

 

(图源网络)

 根据拓扑排序的定义,对AOV网进行拓扑排序的基本思想是:

1)从AOV网中选择一个没有前驱的顶点并输出;

2)从AOV网中删去该顶点以及所有以该顶点为尾的弧;

3)重复上面两步,直到全部顶点都被输出,或AOV网中不存在没有前驱的顶点。

在拓扑排序的过程中,需要查找所有以某顶点为尾的弧,即需要找到该顶点的所有出边,所以图应该采用邻接表储存。另外,在拓扑排序的过程中,需要对某顶点的入度进行操作,例如:查找入度等于零的顶点,将某顶点的入度减1等,而在图的邻接表中对顶点入度的操作不方便,所以,在定点表中增加一个入度域,以方便对入读的操作。

 (图源网络)

 总结:

通过第一周的测验,让我认识到对于一些排列方法掌握的不够熟练,需要在网络中查询相关的知识才会使用,一些题目也是在班级同学的帮助下才完成,在下周的学习中,我也要温故知新,牢牢掌握排序的相关知识。

 

 

 

这篇关于第一次练习总结的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!