欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

常用算法(一)——冒泡排序和双向冒泡排序

程序员文章站 2022-07-12 14:37:26
...

今天回顾了一些常用的算法,总结了一下冒泡和双向冒泡排序。如下:

两种冒泡的原理:
冒泡排序: 嵌套的for循环,外层for控制比较的次数,内层的for控制移动的次数(简单说,就是赋值次数)。通过外层for的(次数)变量的自增,来控制内层for的(索引)变量向0索引逼近。
双向冒泡:定义左右两个索引为0和length-1,通过while循环里面的for循环(控制移动的循环)的索引自增(向右)和自减(向左),将最后一次移动操作后的索引值传递给控制向左和向右比较推荐的left和right两个变量,实现元素的比较向数组中间的逼近,最后当left>right,结束循环即排序结束。特别需要注意的是,外层是循环while别写成if。

效率比较:
如果数据量足够大,双向冒泡是明显要比单向冒泡的效率高的。
常用算法(一)——冒泡排序和双向冒泡排序

下面来看代码:

import java.util.Arrays;

/**
 * Created by Sora on 2018-08-18.
 * 双向冒泡排序: Shaker Sort
 * 左——>右 把大的往后放
 * 右——>左 把小的往前放
 */
public class BubbleAdvancedSort {
    public static void main(String[] args) {
        int[] score = {2,4,3,1,5,3,6,...,2,4,3,1,5,3,6,4};//足够大的数组
        shakerSort(score,score.length);
        System.out.println("最后结果:" + Arrays.toString(score));

        int[] score1 = {2,4,3,1,5,3,6,...,2,4,3,1,5,3,6,4};//足够大的数组
        commonBubble(score1);
        System.out.println("最后结果:" + Arrays.toString(score1));
    }

    public static void shakerSort(int[] arr,int n) {
        int left, right, l, r, i = 0;
        left =0;
        right = n -1;
        long s = System.currentTimeMillis();
        while (left < right) {
            l = left + 1;
            r = right -1;

            //从左往右
            for (i = left; i < right; i++) {
                if (arr[i] > arr[i + 1]) {
                    arr[i] = arr[i] + arr[i + 1] - (arr[i + 1] = arr[i]);
                    r = i;
                }
            }
            right = r;
            //从右往左
            for (i = right; i > left; i--) {
                if (arr[i] < arr[i - 1]) {
                    arr[i] = arr[i] + arr[i - 1] - (arr[i - 1] = arr[i]);
                    //arr[i] = arr[i - 1] + (arr[i - 1] = arr[i]) * 0;
                    l = i;
                }
            }
            left = l;//左边的索引向右移动
        }
        long e = System.currentTimeMillis();
        System.out.println("双向冒泡:"+(e-s)+" 毫秒!");
    }

    //普通冒泡
    public static void commonBubble(int[] arr) {
        int len = arr.length;
        long s = System.currentTimeMillis();
        //比较次数
        for (int i = 0; i < len; i++) {
            //移动次数
            for (int j = 0; j < len - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    //arr[j] = arr[j+1] + (arr[j+1] = arr[j])*0;
                    arr[j] = arr[j] + arr[j + 1] - (arr[j + 1] = arr[j]);
                }
            }
        }
        long e = System.currentTimeMillis();
        System.out.println("普通冒泡:" + (e - s) + " 毫秒!");
    }
}

多次测试后,双向冒泡在性能上都是优于单向冒泡的。
第二次测试
常用算法(一)——冒泡排序和双向冒泡排序
第三次测试
常用算法(一)——冒泡排序和双向冒泡排序

相关标签: 常用算法