JAVA语言的常见排序算法

　　导语：每种排序算法都有它自己的优点及局限性，适用于不同的要求范围，在选择时应根据需要适当选用，甚至可将多种算法结合起来使用，效率才会更高。下面就由小编为大家介绍一下JAVA语言的常见排序算法，欢迎大家阅读!

　　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 sort(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++];