Java数组的排序算法

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

在Java中，实现数组的排序算法有很多，如冒泡排序法、选择排序法、直接插入法和快速排序法、归并排序等。下面介绍几种排序算法的具体实现。

本文引用文献：Java必须知道的300个问题。

1.冒泡排序法

1.1 基本思想：

比较待排序的数据元素中的相邻元素：如果前面的元素大于后面的元素，那么将两个元素交换位置；否则不变。即：永远保持大的元素值在待排序元素中的最后面位置。这样，数组元素就像气泡一样从底部上升到顶部。

1.2 过程实例：

每一轮，排序数组的长度减1次（每一轮结束后，最大元素都是最后一个元素。因此下轮比较过程中最后一次比较不用进行。）

1.3 代码实现

public static void main(String[] args) {
//初始化数组
int[] array = {63,4,24,1,3,13};
//排序
for (int i = 1; i < array.length; i++) {
for (int j = 0; j < array.length - i; j++) {
if(array[j] > array[j+1]){
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
//输出结果
System.out.println(Arrays.toString(array));
}

2. 选择排序法

2.1 基本思想

每一轮从待排序的数据元素中选出最小（最大）的一个元素，将该元素（通过与相邻元素交换的方式）移到待排序的数据元素的最前面（最后面），直到全部待排序的数据元素排完。

2.2 过程实例

2.3 代码实现

//初始化数组
int[] array = {,,,,,};//排序
int len = array.length;
//控制轮数
for (int i = 1; i < len; i++) {
int max = array[];
int index = ;
//查找最大值
for (int j = ; j < len - (i - 1); j++) {
if(max < array[j]){
max = array[j];
index = j;
}
}
//互换位置
int temp = array[index];
array[index] = array[len - i];
array[len - i] = temp;
}//输出
System.out.println(Arrays.toString(array));

3. 直接插入排序法

3.1 基本思想

1. 将n个有序元素放在数组中 --> 2.确认要插入元素的位置 --> 3.将数组中的要插入元素的位置后面的元素向后移一个位置 --> 4.将要出如的元素插到合适的位置上 --> 5.重复2. 3. 4.直到所有元素均插入到数组中。

3.2 过程实例

3.3 代码实现

//初始化数组
int[] array = {20,40,90,30,80,70,50};//排序
int j;
for (int i = 1; i < array.length; i++) {
int temp = array[i];
for (j = i - 1; j > 0 && array[j] > temp; j--) {
array[j+1] = array[j];
}
array[j+1] = temp;
}//输出
System.out.println(Arrays.toString(array));

4. 快速排序法

4.1 基本思想

通过一趟排序将要排序的数据分割成独立的两部分（通常选取中数作为分割线），其中一部分的所有数据都比另一部分的所有数据要小，然后再按此方法对这两部分数据进行快速排序，整个过程可以通过递归进行。

4.2 过程实例

4.3 代码实现

public static void main(String[] args) {
//初始化数组
int[] array = {49,38,65,97,76,13,27,49}; //排序
quickSort(array, 0, array.length - 1); //输出
System.out.println(Arrays.toString(array));}private static void quickSort(int[] array, int lowIndex, int highIndex) {
int lo = lowIndex;
int hi = highIndex;
int mid;
if(highIndex > lowIndex){
mid = array[(lowIndex + highIndex) / 2];
while(lo <= hi){
while((lo < highIndex) && (array[lo] < mid)){
++lo;
}
while(hi > lowIndex && array[hi] >mid){
--hi;
}
if(lo <= hi){
swap(array,lo,hi);
++lo;
--hi;
}
}
if(lowIndex <hi){
quickSort(array, lowIndex, hi);
}
if(lo < highIndex){
quickSort(array, lo, highIndex);
}
}
}private static void swap(int[] array, int lo, int hi) {
int temp = array[lo];
array[lo] = array[hi];
array[hi] = temp;
}

4.4 算法评价

快速排序是通用排序算法的传统选择。

5. 归并排序

5.1 基本思想

将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

5.2 过程实例

将序列拆分成子序列（每个子序列中有两个元素），将每个子序列进行排序（如：第一轮）；然后将拆分后的子序列进行两两合并，如果有落单的子序列，合并入上一组（如：第二轮）。重复合并的逻辑，一直到最后只剩下一个数组（该数组以实现排序），结束。

5.3 代码实现

package com.BlueStarWei.test;public class Test2 { public static void main(String[] args) {
int[] a = new int[]{43, 35, 62, 13, 24, 57,88,91,4,6,34};
mergeSort(a, 0, 1);
for (int i = 0; i < a.length; ++i) {
System.out.print(a[i] + "");
}
} /**
* *<pre>
* *二路归并
* *原理：将两个有序表合并和一个有序表
* *</pre>
* *
* *@parama
* *@paramlow
* *第一个有序表的起始下标
* *@paramlow2
* *第二个有序表的起始下标
* *@paramhight2
* *第二个有序表的结束小标
* *
*/
private static void merge(int[] a, int low, int low2, int hight2) {
//1.分配空间存放比较后的元素
int[] tmp = new int[hight2 - low + 1];
int i = low, j = low2, k = 0;
//2.将较小的元素存入tmp
while (i < low2 && j <= hight2) {
if (a[i] <= a[j]) {
tmp[k] = a[i];
k++;
i++;
} else {
tmp[k] = a[j];
j++;
k++;
}
}
//3.将进行排序的元素中最大的元素存入tmp
while (i < low2) {
tmp[k] = a[i];
i++;
k++;
}
while (j <= hight2) {
tmp[k] = a[j];
j++;
k++;
}
//4.将排好顺序的元素存入a(替代原有元素)
System.arraycopy(tmp, 0, a, low, tmp.length); } /**
* *
* *@parama
* *@paramlow
* 第一个有序表的起始下标
* *@parammergeLen
* * 每一次进行合并的数组长度
*/
public static void mergeSort(int[] a, int low, int mergeLen) {
int size = a.length;
int mid = size / (mergeLen << 1);
//判断进行分割后的数组数量是否是奇数个
int c = size & ((mergeLen << 1) - 1);
//-------归并到只剩一个有序集合的时候结束算法-------//
if (mid == 0)
return;
//------进行一趟归并排序-------//
for (int i = 0; i < mid; ++i) {
low = i * 2 * mergeLen;
merge(a, low, low + mergeLen, (mergeLen << 1) + low - 1);
}
//-------将剩下的数和倒数一个有序集合归并-------//
if (c != 0)
merge(a, size - c - 2 * mergeLen, size - c, size - 1); for (int i = 0; i < a.length; ++i) {
System.out.print(a[i] + "");
}
System.out.println();
//-------递归执行下一趟归并排序------//
mergeSort(a, 0, 2 * mergeLen);
}}