冒泡排序

方法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);
    }
}