这里的冒泡是按照从小到大的顺序来的
思想:将相邻的元素两两比较, 当一个元素大于右侧相邻的元素时,交换他们的位置;当一个元素小于右侧相邻的元素时,不做任何改变。
一、第一种方法
public static void main(String[] args) {
int[] array = new int[]{5, 8, 6, 3, 9, 2, 1, 7};
sort(array);
System.out.println(Arrays.toString(array));
}
private static void sort(int[] arr) {
for (int i = 0; i < arr.length - 1; ++i) {
for (int j = 0; j < arr.length - i - 1; ++j) {
if (arr[j] > arr[j + 1]) {
exchange(arr, j, j + 1);
}
}
}
}
private static void exchange(int[] nums, int i ,int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
二、第二种方法
/**
* 冒泡排序的第二种写法
* 在这种情况下,用一个标记来判断当前数列是否已经有序,若有序,则接下来的排序不必执行,因为已经排好序了
*/
public class BubbleSort02 {
public static void main(String[] args) {
int[] array = new int[]{5, 8, 6, 3, 9, 2, 1, 7};
sort(array);
System.out.println(Arrays.toString(array));
}
private static void sort(int[] arr) {
//有序标记
boolean isSwapped = true;
for (int i = 0; i < arr.length - 1; ++i) {
if (!isSwapped) return;
isSwapped = false;
for (int j = 0; j < arr.length - i - 1; ++j) {
if (arr[j] > arr[j + 1]) {
isSwapped = true;
exchange(arr, j, j + 1);
}
}
}
}
/**
* 数组中元素的交换
*/
private static void exchange(int[] nums, int i ,int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
三、第三种方法
/**
* 冒泡排序的第三种写法
* 1、记录最后一次元素交换的位置
* 2、有序区的界定(无序数列的边界)
*/
public class BubbleSort05 {
public static void main(String[] args) {
int[] arr = new int[]{5, 8, 6, 3, 9, 2, 1, 7};
sort(arr);
System.out.println(Arrays.toString(arr));
}
private static void sort(int[] arr) {
boolean isSwapped = true;
//最后一次元素交换的位置
int lastSwappedIndex = 0;
//无序数列的边界,每次比较只需要比较到这里为止
int disorderBorder = arr.length - 1;
for (int i = 0; i < arr.length - 1; i++) {
if (!isSwapped) return;
isSwapped = false;
for (int j = 0; j < disorderBorder; j++) {
if (arr[j] > arr[j + 1]) {
isSwapped = true;
exchange(arr, j, j + 1);
lastSwappedIndex = j;
}
}
disorderBorder = lastSwappedIndex;
}
}
private static void exchange(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}