java的几种排序方法
一、冒泡排序
冒泡排序的算法是每次比较两个相邻的元素，如果第一个比第二个大，那么就去交换这两个元素。让每一对相邻元素作同样的工作，从开始的第一对到数列最后的一对。针对所有的元素作重复的动作，除了最后一个。持续每次对越来越少的元素重复以上的步骤，直到没有任何一对元素需要再比较。
注意：相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。
import java.util.Arrays;
public class ArraySort {
public static void main(String[] args) {
final var arr = new int[] {34, 4, 56, 17, 90, 65};
// 冒泡排序
bubbleSortWith(arr);
// 打印结果 ( [4, 17, 34, 56, 65, 90] )
System.out.println(Arrays.toString(arr));
}
public static void bubbleSortWith(int[] array) {
// 比较轮数等于数列的长度-1
for (int i = 0; i < array.length - 1; i++) {
// 每轮相邻两数比较的次数会比上轮少，所以这里需要减i
for (int j = 0; j < array.length - 1 - i; j++) {
if (array[j] > array[j + 1]) {
// 替换两个元素
array[j] = array[j] + array[j + 1];
array[j + 1] = array[j] - array[j + 1];
array[j] = array[j] - array[j + 1];
}
}
}
}
}
二、选择法排序
每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序排放已排好的数列的最后，直到全部待排序的数据元素排完。与冒泡法相比较，选择法排序的交换次数要少很多，所以速度会快一些。
注意：选择法排序是一种不稳定的排序方法。
import java.util.Arrays;
public class ArraySort {
public static void main(String[] args) {
final var arr = new int[] {34, 4, 56, 17, 90, 65};
selectSortWith(arr);
// 打印结果 ( [4, 17, 34, 56, 65, 90] )
System.out.println(Arrays.toString(arr));
}
public static void selectSortWith(int[] array) {
// 因为最后一个数是自己，自己跟自己不需要比较，所以要减1
for (int i = 0; i < array. length - 1; i++) {
// 每次参与比较的数
for (int j = i + 1; j < array.length; j++) {
if (array[i] > array[j]) {
// 替换两个元素
array[i] = array[i] + array[j];
array[j] = array[i] - array[j];
array[i] = array[i] - array[j];
}
}
}
}
}
三、插入排序法
插入法排序算法：从后往前找到合适位置后插入
基本思想：每步将一个待排序的记录，按照顺序码大小插入到前面已经排序的序列的合适位置（从后往前找到合适位置），直到全部插入排序完成为止。
插入法排序的操作次数明显要少于冒泡排序和选择排序，所以他的效率要更高。
/*
* 插入法排序操作过程：
* 34, 4, 56, 17, 90, 65
* i = 1 tmp = 4 34, 34, 56, 17, 90, 65
* i = 1 tmp = 4 4, 34, 56, 17, 90, 65
* i = 2 tmp = 56 4, 34, 56, 17, 90, 65
* i = 3 tmp = 17 4, 34, 56, 56, 90, 65
* i = 3 tmp = 17 4, 34, 34, 56, 90, 65
* i = 3 tmp = 17 4, 17, 34, 56, 90, 65
* i = 4 tmp = 90 4, 17, 34, 56, 90, 65
* i = 5 tmp = 65 4, 17, 34, 56, 90, 90
* i = 5 tmp = 65 4, 17, 34, 56, 65, 90
*/
import java.util.Arrays;
public class ArraySort {
public static void main(String[] args) {
final var arr = new int[] {34, 4, 56, 17, 90, 65};
// 插入法排序
insertSortWith(arr);
// echo result
System.out.println(Arrays.toString(arr));
}
public static void insertSortWith(int[] array) {
for (int i = 1; i < array.length; i++) { // 控制轮数
final var tmp = array[i]; // 记录数
var j = 0;
for (j = i -1; j >= 0; i--) { // j是i的前一个数所以是-1，因为每次从后往前比较所以j--
if (array[j] > tmp) { // 如果说每次记录数前面的数大于记录数
array[j + 1] = array[j]; // 每次将记录数前面的数与每次的操作数前面的数交换
}
else { // 否则(每次操作数前面的数小于记录数)
break; // 就退出循环
}
}
if (array[j + 1] != tmp) { // 如果记录数最前面的操作数不等于记录数
array[j + 1] = tmp; // 就将其换成记录数
}
}
}
}
四、反转排序
反转排序就是以相反的顺序把原数组的内容重新排序。反转排序在我们的开发当中也经常用到。反转排序的思想就是把数组的最后一个元素和第一个元素进行替换，倒数第二个元素和第二个元素进行替换，以此类推。反转排序的操作次数明显的更少，所以它的效率更高。
注意：反转排序只适合有序的数列进行反转，否则数组最后还是乱的。
import java.util.Arrays;public
class ArraySort {
public static void main(String[] args) {
final var arr = new int[] {10, 20, 30, 40, 50, 60}; reverseSortWith(arr);
// 打印结果( [60, 50, 40, 30, 20, 10] )
System.out.println(Arrays.toString(array));
}
public static void reverseSortWith(int[] array) {
// 反转排序只需要操作数组个数的一半就可以了
final var len = array.length;
for (int i = 0; i < len / 2; i++) {
// 替换元素
array[i] = array[i] + array[len - 1 - i];
array[len - 1 - i] = array[i] + array[len - 1 - i];
array[i] = array[i] - array[len - 1 - i];
}
}
}
网友评论