冒泡排序优化前的平均时间复杂度为O(n²)，是一种稳定排序。
以下代码来自漫画书《小灰算法》感兴趣的小伙伴可以考虑去看一下呦。
思想理解
冒泡排序的思想，我们要把相邻的元素两两比较，当一个元素大于右侧相邻元素时，交换它们的位置；当一个元素小于或等于右侧相邻元素时，位置不变。
- 把相邻的两个元素两两比较，当一个元素大于右侧相邻元素时交换他们的位置，否则位置不变。
- 属于稳定排序。如果没有任何优化操作，遍历次数是（元素数量-1）次。
- 双for循环： 外部循环控制所有回合，内部循环实现每一轮的冒泡处理
- 优化 时间复杂度 希尔排序（性能优于O(n²)，次于O(nlogn)）
import java.util.Arrays;
public class 冒泡排序一 {
public static void sort(int array[]) {
for (int i = 0; i < array.length - 1; i++) {
for (int j = 0; j < array.length - i - 1; j++) {
int tmp = 0;
if (array[j] > array[j + 1]) {
tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
}
}
}
}
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));
}
}
优化一排除前面有序
很明显可以看出，经过第6轮排序后，整个数列已然是有序的了。可是排序算法仍然兢兢业业地继续执行了第7轮排序。
import java.util.Arrays;
public class 冒泡排序第二版 {
public static void main(String[] args) {
int[] array = new int[]{3,4,2,1,5,6,7,8};
sort(array);
System.out.println(Arrays.toString(array));
}
public static void sort(int array[]) {
for (int i = 0; i < array.length - 1; i++) {
//有序标记，每一轮的初始值都是true
boolean isSorted = true;
for (int j = 0; j < array.length - 1-i; j++) {
int tmp = 0;
if (array[j] > array[j + 1]) {
tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
// 因为有元素进行交换，所以不是有序的，标记变为
isSorted = false;
}
}
if (isSorted) {
break;
}
}
}
}
优化二排除后面有序
这里第一轮结束，后面部分 相临元素还会继续进行比较而位置不变，浪费资源
优化代码如下
优化 时间复杂度 希尔排序（性能优于O(n²)，次于O(nlogn)）
- 防止最后几次排序时前面已经有序重的复标记。2.防止后面有序的重复标记
- 标记前面是否有序 若已经有序直接终止大循环，就不用在比较一次了。
- 标记最后一次交换（说明后面的已经都有序）的位置 lastExchangeIndex，下次从这里开始 即 sortBorder=lastExchangeIndex。
import java.util.Arrays;
public class 冒泡排序第三版 {
public static void main(String[] args) {
int[] array = new int[]{3,4,2,1,5,6,7,8};
sort(array);
System.out.println(Arrays.toString(array));
}
public static void sort(int array[]) {
//记录最后一次交换的位置
int lastExchangeIndex = 0;
//无序数列的边界，每次比较只需要比到这里为止
int sortBorder = array.length - 1;
for (int i = 0; i < array.length - 1; i++) {
//有序标记，每一轮的初始值都是true
boolean isSorted = true;
for (int j = 0; j < sortBorder; j++) {
int tmp = 0;
if (array[j] > array[j + 1]) {
tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
// 因为有元素进行交换，所以不是有序的，标记变为
isSorted = false;
// 更新为最后一次交换元素的位置
lastExchangeIndex = j;
}
}
sortBorder = lastExchangeIndex;
if (isSorted) {
break;
}
}
}
}
继续优化三——鸡尾酒
- 鸡尾酒排序的元素比较和交换过程是双向的。
- 排序过程就像钟摆一样，第1轮从左到右，第2轮从右到左，第3轮再从左到右……
import java.util.Arrays;
public class 鸡尾酒排序 {
public static void main(String[] args) {
int[] array = new int[]{3,4,2,1,5,6,7,8};
sort(array);
System.out.println(Arrays.toString(array));
}
public static void sort(int array[]) {
for (int i = 0; i < array.length - 1; i++) {
//有序标记，每一轮的初始值都是true
boolean isSorted = true;
for (int j = 0; j < array.length - 1-i; j++) {
int tmp = 0;
if (array[j] > array[j + 1]) {
tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
// 因为有元素进行交换，所以不是有序的，标记变为
isSorted = false;
}
}
if (isSorted) {
break;
}
}
}
}
评论区