侧边栏壁纸
博主头像
SeaDream乄造梦

Dream,Don't stop a day of hard and don't give up a little hope。 ——不停止一日努力&&不放弃一点希望。

  • 累计撰写 39 篇文章
  • 累计创建 20 个标签
  • 累计收到 13 条评论

目 录CONTENT

文章目录

java排序算法 冒泡排序&&冒泡排序的优化&&冒泡排序的升级-鸡尾酒排序

SeaDream乄造梦
2022-02-21 / 0 评论 / 0 点赞 / 579 阅读 / 2,535 字
温馨提示:
亲爱的,如果觉得博主很有趣就留下你的足迹,并收藏下链接在走叭

冒泡排序优化前的平均时间复杂度为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;
            }
        }
    }
}
0

评论区