基干JAVA语言常见排序算法探析及比较

《基干JAVA语言常见排序算法探析及比较》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、基干JAVA语言常见排序算法探析及比较摘要：该文主要阐述了冒泡排序、插入排序、选择排序、归并排序这4种排序算法的基本思想、JAVA实现代码，通过分析对比得到各种算法的最佳使用场景，从而提高排序的效率关键词：排序算法基本思想性能比较中图分类号：TP312文献标识码：A文章编号：1674-098X(2016)09(c)-0097-03AnalysisandComparisonofCommonSortingAlgorithmsBasedonJAVALanguageXiKefang(JinkenCollegeofTechnology,Nanjing,Jiangsu,210000,Chi

2、na)Abstract:Thisarticlemainlyexpoundsthebubblesort,insertionsort,selectionsort,mergesort,thebasicideaofthefourkindsofsortingalgorithmJavaim中的排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。而排序算法则是一种能将一串数据依照特定的方式进行排序的一种算法根据排序过程中涉及的存储器不同，可以将排序方法分为两大类：一类是内部排序，指的是待排序地记录存放在计算机随机存储器中进行的排序过程。另一类是外部排序，指的是

3、需要对外存储器进行访问的排序过程。该课题主要研究几类常见的内部排序，有冒泡排序、插入排序、选择排序、归并排序2常见排序算法基本思想和JAVA代码实现2.1冒泡排序2.1.1基本思想冒泡排序是将相邻的两个记录按关键值两两比较，如果记录的次序相反时即进行交换，直到序列中不存在反序的记录为止。如有n个无序数，第一趟将第一个和第二个进行比较，将大的放在第二个位置，再将第二个和第三比较，大的放在第三个位置，依次向后比较，比较次，将最大的放在最后（n的位置）；第二趟，再从第一个开始比较，比较n-2次，这次把最大的放到第n-1个位置，然后再来回比较。遵循第i次遍历就从第一个数开始比较n-i次

4、，将最后的值放在第n-i+1的位置。如图1、图2所示2.1.2JAVA语言实现冒泡排序核心代码〃冒泡排序：10万个随机数用时约25秒publicstaticvoidbubblesort(inta[]){inti,j,temp;intn=aolength;〃获得数组长度for(i=1;ia[j+1]){//如果相邻两数前者比后者大，那交temp=a[j];aD]=a[j+1];a[j+1]=temp;}}}}2.2插入排序2.2.1基本思想插入排序是一种简单的排序方法，它的基本排序思想是依次将待排序的记录逐一地按其关键字值的大小插入到一个已排好序的有序序列中，得到一个新的有序序列

5、，直到所有的记录插完为止，从而实现排序。在有序情况下只需要经过n-1次比较，在最坏情况下，将需要n(n-1)/2次比较，如图3所示2.2.2JAVA语言实现插入排序核心代码〃插入排序：10万随机数据用时约7秒publicstaticvoidinsertsort(int[]arr){〃插入排序：从小到大，从前往后，先找位置后排序〃外层循环确定轮次：从第二个到最后一个，门畀轮intj;for(inti=1;i〃内存循环先找位置：从后(i-1)前for(j=i-1;j>=0;j—){〃如果找到了比当前数小的，退出〃三种情况都确定了j+1为当前数应该排的位置if(arr[j]break

6、;}}〃再交换排序inttemp=arr[i];〃从[j+1,i-1]通通往后退一格for(intk=i-1;k>=j+1;k-){arr[k+1]=arr[k];}//j+1这个位置让我排arr[j+1]=temp;}}2.3选择排序2.3.1基本思想选择排序是在待排序的一组数据元素中，选出最小的一个数据元素与第一个位置的数据元素交换；然后在剩下的数据元素当中再找最小的与第二个位置的数据元素交换，循环到只剩下最后一个数据元素为止。它的比较次数是一定的：n(n-1)/2o因此无论何种序列，正序和反序数据耗时相差不多，相差的只是数据移动时间，对数据的有序性不敏感。它虽然比较次数多

7、，但它的数据交换量却很少。如图4所示2.3.2JAVA语言实现选择排序核心代码〃选择排序：10万随机数据用时约8秒publicstaticvoidselectsort(int[]arr){〃外层循环确定轮次(n-1)intmin;intindex;for(inti=0:i〃内层循环确定比较和交换范围min=arr[i];index=i;for(intj=i+1;j〃比较和交换if(min>arr[j]){min=arr[j];index=j;}}if(i!=index){inttemp=ar