基于java语言的常见排序算法分析与比较

《基于java语言的常见排序算法分析与比较》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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

2、　（JinkenCollegeofTechnology，Nanjing，Jiangsu，210000，China）　　Abstract：Thisarticlemainlyexpoundsthebubblesort，insertionsort，selectionsort，mergesort，thebasicideaofthefourkindsofsortingalgorithmJavaimplementationcode，wewouldgetthebestuseofthesceneandimprove

3、theefficiencyofthesortthroughtheanalysisandcomparisonofvariousalgorithms.　　KeyWords：Sortingalgorithm；Basicidea；Performancecomparison　　1排序算法概述　　所?^计算机中的排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。而排序算法则是一种能将一串数据依照特定的方式进行排序的一种算法。　　根据排序过程中涉及的存储器不同，可以将排序方法分为

4、两大类：一类是内部排序，指的是待排序地记录存放在计算机随机存储器中进行的排序过程。另一类是外部排序，指的是需要对外存储器进行访问的排序过程。该课题主要研究几类常见的内部排序，有冒泡排序、插入排序、选择排序、归并排序。　　2常见排序算法基本思想和JAVA代码实现　　2.1冒泡排序　　2.1.1基本思想　　冒泡排序是将相邻的两个记录按关键值两两比较，如果记录的次序相反时即进行交换，直到序列中不存在反序的记录为止。如有n个无序数，第一趟将第一个和第二个进行比较，将大的放在第二个位置，再将第二个和第三比较，

5、大的放在第三个位置，依次向后比较，比较n-1次，将最大的放在最后（n的位置）；第二趟，再从第一个开始比较，比较n-2次，这次把最大的放到第n-1个位置，然后再来回比较。遵循第i次遍历就从第一个数开始比较n-i次，将最后的值放在第n-i+1的位置。如图1、图2所示。　　2.1.2JAVA语言实现冒泡排序核心代码　　//冒泡排序：10万个随机数用时约25秒　　publicstaticvoidbubblesort（inta[]）{　　inti，j，temp；　　intn=a。length；//获得数组长度

6、　　for（i=1；i<=n；i++）{//外层循环控制比较趟数　　for（j=0；ja[j+1]）{//如果相邻两数前者比后者大，那交换　　temp=a[j]；　　a[j]=a[j+1]；　　a[j+1]=temp；　　}　　}　　}　　}　　2.2插入排序　　2.2.1基本思想　　插入排序是一种简单的排序方法，它的基本排序思想是依次将待排序的记录逐一地按其关键字值的大小插入到一个已排好序的有序序列中，得到一个新的有序序列，直到所

7、有的记录插完为止，从而实现排序。在有序情况下只需要经过n-1次比较，在最坏情况下，将需要n（n-1）/2次比较，如图3所示。　　2.2.2JAVA语言实现插入排序核心代码　　//插入排序：10万随机数据用时约7秒　　publicstaticvoidinsertsort（int[]arr）{　　//插入排序：从小到大，从前往后，先找位置后排序　　//外层循环确定轮次：从第二个到最后一个，n-1轮　　intj；　　for（inti=1；i　　//内存循环先找位置：从后（i-1）前找，最多找到0　　for

8、（j=i-1；j>=0；j--）{　　//如果找到了比当前数小的，退出//三种情况都确定了j+1为当前数应该排的位置　　if（arr[j]　　break；　　}　　}　　//再交换排序　　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基本思想　　选择