Java的集中基本常用算法.docx

《Java的集中基本常用算法.docx》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、1.常用算法1.1.冒泡排序算法冒泡排序是排序算法的一种，思路清晰，代码简洁，常被用在大学生计算机课程中。“冒泡”这个名字的由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端，故名。这里以从小到大排序为例进行讲解1.1.1.基本思想及举例说明冒泡排序的基本思想就是不断比较相邻的两个数，让较大的元素不断地往后移。经过一轮比较，就选出最大的数；经过第2轮比较，就选出次大的数，以此类推。下面以对3241进行冒泡排序说明。第一轮排序过程3241（最初）2342（比较3和2，交换）2341（比较3和4，不交换）2314（比较4和1，交换）第一轮结束，最大的数4已经在最后

2、面，因此第二轮排序只需要对前面三个数进行再比较。第二轮排序过程2314（第一轮排序结果）2314（比较2和3，不交换）2134（比较3和1，交换第二轮结束，第二大的数已经排在倒数第二个位置，所以第三轮只需要比较前两个元素。第三轮排序过程2134（第二轮排序结果）1234（比较2和1，交换）至此，排序结束。1.1.1.算法总结及实现对于具有N个元素的数组R[n]，进行最多N-1轮比较；第一轮，逐个比较（R[1],R[2]）,（R[2],R[3]）,（R[3],R[4]）,…….（R[N-1],R[N]）;最大的元素会被移动到R[N]上。第二轮，逐个比较（R[1],

3、R[2]）,（R[2],R[3]）,（R[3],R[4]）,…….（R[N-2],R[N-1]）；第二大元素会被移动到R[N-1]上。。。。。以此类推，直到整个数组从小到大排序。下面给出了冒泡排序的一般实现和优化实现。一般实现是教科书里常见的实现方法，无论数组是否排序好了，都会进行N-1轮比较；而优化实现，在数组已经排序好的情况下，会提前退出比较，减小了算法的时间复杂度。/**Createdon:2015年4月25日*Author:xia*/#include#include#defineN8voidbubble_sort(i

4、nta[],intn);//一般实现Voidbubble_sort(inta[],intn)//n为数组a的元素个数{//一定进行N-1轮比较for(inti=0;ia[j+1]){inttemp=a[j];a[j]=a[j+1];a[j+1]=temp;}}}}//优化实现voidbubble_sort_better(inta[],intn)//n为数组a的元素个数{//最多进行N-1轮比较for(inti=0;i

5、1;i++){intisSorted=1;//每一轮比较前n-1-i个，即已排序好的最后i个不用比较for(intj=0;ja[j+1]){isSorted=0;inttemp=a[j];a[j]=a[j+1];a[j+1]=temp;}}if(isSorted)break;//如果没有发生交换，说明数组已经排序好了}}intmain(){intnum[N]={89,38,11,78,96,44,19,25};bubble_sort(num,N);//或者使用bubble_sort_better(num,N);for(in

6、ti=0;i

7、1轮排序过程（寻找第1小的数所在的位置）3241（最初，min_index=1）3241（3>2，所以min_index=2）3241（2<4，所以min_index=2）3241（2>1，所以min_index=4，这时候确定了第1小的数在位置4）1243（第1轮结果，将3和1交换，也就是位置1和位置4交换）第2轮排序过程（寻找第2小的数所在的位置）1243（第1轮结果，min_index=2，只需要从位置2开始寻找）1243（4>2，所以min_index=2）1243（3>2，所以min_index=2）1243（第2轮结果，因为min_index位置刚好

8、在第2个位置，无需交换）