【算法】冒泡排序

kel 发布于2019-08-16 18:00 / 732人阅读

摘要：简单实现左边是大不是正常的排序顺序的做交换考虑优化优化冒泡排序优化版本，节约有序的第一轮，永远是找到最大的第二轮，找到的是第二大的，所以右边个永远是有序的如果有一种特殊情况，右边经过对比，发现不需要交换了，那就是后面的都是最大的。

No bb . Show me the code

1. 简单实现

public static long sort(int[] intArr) {
        int  arrLen     = intArr.length;
        long recycleNum = 0;
        if (0 == arrLen) {
            return recycleNum;
        }
        for (int i = 0; i < arrLen; i++) {
            for (int j = 0; j < arrLen - 1; j++) {
                recycleNum++;
                // 左边是大（不是正常的排序顺序）的做交换
                if (intArr[j] > intArr[j + 1]) {
                    int temp = intArr[j];
                    intArr[j] = intArr[j + 1];
                    intArr[j + 1] = temp;
                }
            }
        }

        return recycleNum;
    }

考虑优化

2. 优化

/**
     * 冒泡排序-优化版本，节约有序的
     *
     * @param intArr
     */
    public static long sortPlus(int[] intArr) {
        // 第一轮，永远是找到最大的
        // 第二轮，找到的是第二大的，所以右边 n 个永远是有序的
        // 如果有一种特殊情况，右边经过对比，发现不需要交换了，那就是后面的都是最大的。 有一个不是前面对比最大的，就会发生交换

        // 加一个标记位，不发生交换的位置，就是比较的end
        // 这样 原则上 1，2，3，4，5，6，7，8 只需要比较一轮
        int  arrLen     = intArr.length;
        long recycleNum = 0;
        if (0 == arrLen) {
            return recycleNum;
        }
        boolean isSorted = true;
        for (int i = 0; i < arrLen; i++) {
            for (int j = 0; j < arrLen - 1; j++) {
                recycleNum++;
                // 左边是大（不是正常的排序顺序）的做交换
                if (intArr[j] > intArr[j + 1]) {
                    int temp = intArr[j];
                    intArr[j] = intArr[j + 1];
                    intArr[j + 1] = temp;
                    // 发生了交换
                    isSorted = false;
                }
            }
            // TODO mark 是不是 j 都遍历一遍 只是增加了 判断。 反而增加了逻辑判断
            if (isSorted) {
                break;
            }
        }
        return recycleNum;
    }

3. 有序区

/**
     * 冒泡排序-有序区
     *
     * @param intArr
     */
    public static long sortOrdered(int[] intArr) {
        int  arrLen            = intArr.length;
        int  lastExchangeIndex = arrLen;
        int  sortLen           = arrLen - 1;
        long recycleNum        = 0;
        if (0 == arrLen) {
            return recycleNum;
        }

        boolean isSorted = true;
        for (int i = 0; i < arrLen; i++) {
            for (int j = 0; j < sortLen; j++) {
                recycleNum++;
                // 左边是大（不是正常的排序顺序）的做交换
                if (intArr[j] > intArr[j + 1]) {
                    int temp = intArr[j];
                    intArr[j] = intArr[j + 1];
                    intArr[j + 1] = temp;
                    // 发生了交换
                    isSorted = false;

                    // 排序后的位置一定是有序的期间
                    lastExchangeIndex = j;
                }
            }

            // 节约空间，如果已经有序，不对比那么多，缩短长度
            // 为了不影响 j 循环，循环结束后引入新的变量
            sortLen = lastExchangeIndex;
            if (isSorted) {
                break;
            }
        }
        return recycleNum;
    }

4. 测试代码

/**
 * 循环次数，测试性能
 */
private static final int NUM = 1;

public static void main(String[] args) {
    //获取开始时间
    long startTime = System.currentTimeMillis();

    for (int i = 0; i < NUM; i++) {
        int[] intArr = new int[]{3, 4, 2, 1, 5, 6, 7, 8, 11};
        // 72
        //            long recycleNum = sort(intArr);
        // 72
        long recycleNum = sortPlus(intArr);
        // 11
        //            long recycleNum = sortOrdered(intArr);
        System.out.println("循环次数:" + recycleNum);
        //  System.out.println(Arrays.toString(intArr));
    }
    // 获取结束时间
    long endTime = System.currentTimeMillis();
    System.out.println("程序运行时间： " + (endTime - startTime) + "ms");
}

云服务器 GPU云服务器冒泡排序前端冒泡排序冒泡排序代码 js冒泡排序

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/74883.html

JavaScript 数据结构与算法之美 - 冒泡排序、插入排序、选择排序

摘要：之所以把冒泡排序选择排序插入排序放在一起比较，是因为它们的平均时间复杂度都为。其中，冒泡排序就是原地排序算法。所以冒泡排序是稳定的排序算法。选择排序思路选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言算法为王。想学好前端，先练好内功，...

canger 2019-08-26 10:15 评论0 收藏0
数据结构与算法——冒泡排序

摘要：多练练排序算法，不仅能够让我们知道一些排序方法的底层实现细节，更能够锻炼我们的思维，提升编程能力。排序算法的稳定性一个稳定的排序，指的是在排序之后，相同元素的前后顺序不会被改变，反之就称为不稳定。 1. 导言因为这是排序算法系列的第一篇文章，所以多啰嗦几句。排序是很常见的算法之一，现在很多编程语言都集成了一些排序算法，比如Java 的Arrays.sort()方法，这种方式让我们可...

Yang_River 2019-08-16 15:51 评论0 收藏0
排序算法分析总结（附js实现）

摘要：本文对一些排序算法进行了简单分析，并给出了的代码实现。平均时间复杂度不好分析，它是冒泡排序是稳定的排序算法。冒泡排序是原地排序算法原地排序指的是空间复杂度是的排序算法。归并排序，会将数组从中间分成左右两部分。本文对一些排序算法进行了简单分析，并给出了 javascript 的代码实现。因为本文包含了大量的排序算法，所以分析不会非常详细，适合有对排序算法有一定了解的同学。本文内容其实不...

liaoyg8023 2019-08-23 17:11 评论0 收藏0
数据结构与算法（二）：带你读懂冒泡排序（Bubble Sorting）

摘要：经过一次冒泡排序，最终在无序表中找到一个最大值，第一次冒泡结束。也是我们后面要说的冒泡排序的优化。冒泡排序只执行第一层循环，而不会执行第二层循环。因此冒泡排序的时间复杂度是。 showImg(https://user-gold-cdn.xitu.io/2019/6/19/16b6f986df6880f9?w=640&h=142&f=gif&s=17175);showImg(https:...

chuyao 2019-08-19 11:46 评论0 收藏0
算法之旅 | 冒泡排序法

摘要：学堂码匠本期继续走入算法冒泡排序法。冒泡排序法完整代码冒泡排序法的优化假如序列的数据为使用上面的冒泡排序法进行排序，得到的结果肯定没有问题，但是，待排序的序列是有序的，理论上是无需遍历排序。 HTML5学堂-码匠：本期继续走入算法 —— 冒泡排序法。冒泡排序算法相对简单，容易上手，稳定性也比较高,算是一种较好理解的算法，也是面试官高频提问的算法之一。 Tips：关于算法及排序的基础知识...

qujian 2019-08-20 19:05 评论0 收藏0