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

奚科芳

摘 要：该文主要阐述了冒泡排序、插入排序、选择排序、归并排序这4种排序算法的基本思想、JAVA实现代码，通过分析对比得到各种算法的最佳使用场景，从而提高排序的效率。

关键词：排序算法 基本思想 性能比较

中图分类号：TP312 文献标识码：A 文章编号：1674-098X（2016）09（c）-0097-03

Analysis and Comparison of Common Sorting Algorithms Based on JAVA Language

Xi Kefang

（Jinken College of Technology，Nanjing，Jiangsu，210000，China）

Abstract：This articlemainly expounds the bubble sort， insertion sort， selection sort， merge sort， the basic idea of the four kinds of sorting algorithm Java implementation code，we would get the best use of the scene and improve the efficiency of the sortthrough the analysis and comparison of various algorithms.

Key Words：Sorting algorithm；Basic idea；Performance comparison

1 排序算法概述

所謂计算机中的排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。而排序算法则是一种能将一串数据依照特定的方式进行排序的一种算法。

根据排序过程中涉及的存储器不同，可以将排序方法分为两大类： 一类是内部排序，指的是待排序地记录存放在计算机随机存储器中进行的排序过程。另一类是外部排序，指的是需要对外存储器进行访问的排序过程。该课题主要研究几类常见的内部排序，有冒泡排序、插入排序、选择排序、归并排序。

2 常见排序算法基本思想和JAVA代码实现

2.1 冒泡排序

2.1.1 基本思想

冒泡排序是将相邻的两个记录按关键值两两比较，如果记录的次序相反时即进行交换，直到序列中不存在反序的记录为止。如有n个无序数，第一趟将第一个和第二个进行比较，将大的放在第二个位置，再将第二个和第三比较，大的放在第三个位置，依次向后比较，比较n-1次，将最大的放在最后（n的位置）；第二趟，再从第一个开始比较，比较n-2次，这次把最大的放到第n-1个位置，然后再来回比较。遵循第i次遍历就从第一个数开始比较n-i次，将最后的值放在第n-i+1的位置。如图1、图2所示。

2.1.2 JAVA语言实现冒泡排序核心代码

//冒泡排序：10万个随机数用时约25秒

public static voidbubblesort （int a[]）{

inti，j，temp；

int n=a。length； //获得数组长度

for（i=1；i<=n；i++）{ //外层循环控制比较趟数

for（ j=0；j

if（a[j]>a[j+1]）{//如果相邻两数前者比后者大，那交换

temp=a[j]；

a[j]=a[j+1]；

a[j+1]=temp；

}

}

}

}

2.2 插入排序

2.2.1 基本思想

插入排序是一种简单的排序方法，它的基本排序思想是依次将待排序的记录逐一地按其关键字值的大小插入到一个已排好序的有序序列中，得到一个新的有序序列，直到所有的记录插完为止，从而实现排序。在有序情况下只需要经过n-1次比较，在最坏情况下，将需要n（n-1）/2次比较，如图3所示。

2.2.2 JAVA语言实现插入排序核心代码

//插入排序：10万随机数据用时约7秒

public static void insertsort（int[] arr） {

//插入排序：从小到大，从前往后，先找位置后排序

//外层循环确定轮次：从第二个到最后一个，n-1轮

int j；

for（inti=1； i

//内存循环先找位置：从后（i-1）前找，最多找到0

for（j=i-1； j>=0； j--） {

//如果找到了比当前数小的，退出//三种情况都确定了j+1为当前数应该排的位置

if（arr[j]

break；

}

}

//再交换排序

int temp = arr[i]；

//从[j+1，i-1]通通往后退一格

for（int k=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）/2。因此无论何种序列，正序和反序数据耗时相差不多，相差的只是数据移动时间，对数据的有序性不敏感。它虽然比较次数多，但它的数据交换量却很少。如图4所示。

2.3.2 JAVA语言实现选择排序核心代码

//选择排序：10万随机数据用时约8秒

public static void selectsort（int[] arr） {

//外层循环确定轮次（n-1）

int min；

int index；

for（inti=0； i

//内层循环确定比较和交换范围

min = arr[i]；

index = i；

for（int j=i+1；j

//比较和交换

if（min >arr[j]） {

min = arr[j]；

index = j；

}

}

if（i ！= index） {

int temp = arr[i]；

arr[i] = arr[index]；

arr[index] = temp；

}

}

}

2.4 归并排序

2.4.1 基本思想

归并排序要求待排序列已经部分有序。部分有序的含义是待排序列由若干个有序的子序列组成。归并排序的基本思想是：将这些有序的子序列进行合并，从而得到有序的序列。合并是一种常见运算，其方法是：比较各子序列的第一个记录的键值，最小的一个就是排序后序列的第一个记录的键值。取出这个记录，继续比较各子序列现在的第一个记录的键值，便可找出排序后的第二记录。如此继续下去，最终可以得到排序结果。因此，归并排序的基础是合并，如图5所示。

2.4.2 JAVA 语言实现归并排序核心代码

//归并排序：10万随机数据用时约15毫秒

public static void merge（int[] arr，int from，int mid，int end，int[] temp） {

//分配大数组空间

//int[] arr = new int[a。length+b。length]；

//定义三个下标分别指向a，b，arr

inti=from，j=mid+1，k=from；

//比较，取值，直到其中一个数组结束

while（i<=mid && j<=end） {

if（arr[i]

temp[k++] = arr[i++]；

}else {

temp[k++] = arr[j++]；

}

}

while（i<=mid） {

temp[k++] = arr[i++]；

}

while（j<=end） {

temp[k++] = arr[j++]；

}

for（int index=from；index<=end；index++） {

arr[index] = temp[index]；

}

}

public static void sort（int[] arr，int from，int to，int[] temp） {

if（from < to） {

int mid = （from+to）/2；

//递归

sort（arr，from，mid，temp）；

sort（arr，mid+1，to，temp）；

//合并

merge（arr，from，mid，to，temp）；

}

}

3 排序方法的性能比较及选择

3.1 性能对比

我们可以通过一些基本的性能标准对各个排序方法进行总结对比，见表1。

3.2 影响排序效果的因素

上述介绍的4种排序方法，因为不同的排序方法适应不同的应用环境和要求，所以选择合适的排序方法应综合考虑下列因素：

①待排序的记录数目n；

②记录的大小（规模）；

③关键字的结构及其初始状态；

④对稳定性的要求；

⑤语言工具的条件；

⑥存儲结构；

⑦时间和辅助空间复杂度等。

3.3 排序方法的选择

①若n较小（如n≤50），可采用插入排序或选择排序。当记录规模较小时，插入排序较好；否则因为选择排序移动的记录数少于插人排序，应选选择排序为宜。

②若文件初始状态基本有序（指正序），则应选用插人排序、冒泡排序为宜；

②若n较大，则应采用时间复杂度为O（nlgn）的排序方法：归并排序。

综上所述，在上述排序算法中，不能绝对地说哪个算法是最好的。每种排序算法都有它自己的优点及局限性，适用于不同的要求范围，在选择时应根据需要适当选用，甚至可将多种算法结合起来使用，效率才会更高。

参考文献

[1] 谢婷.基于C语言的常用排序算法比较[J].湖南城学院学报：自然科技版，2016，25（4）：95-96.

[2] 赵雅青，徐燕.数值排序算法比较分析[J].电脑编程技术与维护，2015（23）：5-7.

[3] 李梅云.一些常见数据排序算法的比较[J].漳州职业技术学院学报，2009（7）：60-62.