Java算法-排序算法-阿里云开发者社区

开发者社区> 人工智能> 正文

Java算法-排序算法

简介:

冒泡排序

方法sort是基本的冒泡排序, sort1/sort2是冒泡排序的两种优化

package me.zx.algorithm.program.sort;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * 冒泡排序.
 * Created by zhangxin on 2017/12/27.
 *
 * @author zhangxin
 * @since 0.0.1
 */
public final class BubbleSort {

    private static final Logger LOGGER = LoggerFactory.getLogger(BubbleSort.class);

    /**
     * 基本的冒泡排序.
     * @param a 待排序数组
     */
    public static void sort(int[] a) {
        int temp = 0;
        for(int i = a.length - 1; i > 0; i--) {
            for(int j = 0; j < i; j++) {
                if(a[j + 1] < a[j]) {
                    temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                }
            }
        }
    }

    /**
     * 优化的冒泡排序1.
     * 当某一趟遍历没有交换,就说明已经遍历好了,就不用再迭代了
     * @param a 待排序数组
     */
    public static void sort1(int[] a) {
        int temp = 0;
        boolean sorted = false;
        for(int i = a.length - 1; i > 0; i--) {
            sorted = false; //初始值设置为未排序
            for(int j = 0; j < i; j++) {
                if(a[j + 1] < a[j]) {
                    temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                    sorted = true; //发生排序时重新设值
                }
            }
            if(!sorted){
                //当经过一次遍历没有发生一次排序, 或者上次排序位置与本次排序位置相同
                break;
            }
        }
    }
    /**
     * 优化的冒泡排序2.
     * 记录每次遍历数据之后交换次序的位置,显然这个位置之后的数据已经有序了不用再排序了。因此通过记录最后发生数据交换的位置就可以确定下次循环的范围了
     * @param a 待排序数组
     */
    public static void sort2(int[] a) {
        int temp = 0;
        int lastChangeLocation; //上次排序发生的位置
        int nowChangeLocation = a.length - 1; //本次排序发生的位置
        for(int i = a.length - 1; i > 0; i--) {
            lastChangeLocation = nowChangeLocation;
            for(int j = 0; j < i; j++) {
                if(a[j + 1] < a[j]) {
                    temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                    nowChangeLocation = j; //发生排序时重新设值
                }
            }
            if(lastChangeLocation == nowChangeLocation){
                //当经过一次遍历没有发生一次排序, 或者上次排序位置与本次排序位置相同
                break;
            }
        }
    }



    public static void main(final String[] args){
//        int[] a = {0, 1, 2, 3, 4, 5, 6};
        int[] a = {6, 5, 4, 3, 2, 1, 0};
        LOGGER.info("原数组:{}", a);
        sort1(a);
        LOGGER.info("现数组:{}", a);
    }
}

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章