冒泡排序

2020-04-17  本文已影响0人  c97e4a46b0c0

引言

做程序员已经差不多两年多的时间了,但是在工作中基本都是框架和调用API,也没有进行对于底层技术或者其原理进行学习,至此到今日,每天记录一下自己的学习过程,来加深自己对于技术的沉淀;不管是对于平时遇到的问题的解决方式,或者是对有些含糊不清的地方得以解释,我都会进行记录,如果有什么不对的地方,请直接给我留言就行;

基类使用

在写排序之前,我自己封装了一个通用的基础类,以便在后续的代码中,能提高阅读性;

package com.sladar;

/**
 * tips: this is the base class for sorting function,It contains the swap position
 * function, compare size function, check whether it is a positive order function
 * and print each element function in the array;
 * the class using int array as base comparable element, if you want to do a compare
 * method on Object, u can implements Comparable ${ @see Comparable.Class }
 * @Author create by MoYang
 * @Time 2019-13-30 23:29
 * @Email xiaojiju0811@163.com
 */
public abstract class BaseCompare {
    /**
     * sort array
     * @param comparable enable compare element array
     */
    public abstract void sort(int[] comparable);

    /**
     * compare two array
     * @param v
     * @param w
     * @return
     */
    public static boolean less(int v, int w) {
        return v < w;
    }

    /**
     * exchange position
     * @param comparable
     * @param i
     * @param j
     */
    public static void exch(int[] comparable, int i, int j) {
        int t = comparable[i];
        comparable[i] = comparable[j];
        comparable[j] = t;
    }

    /**
     * print each element in array
     * @param comparable
     */
    public static void show(int[] comparable) {
        for (int i = 0; i < comparable.length; i++) {
            System.out.print(comparable[i] + " ");
        }
        System.out.println();
    }

    /**
     * check position order
     * @param comparable
     * @return
     */
    public static boolean isSort(int[] comparable) {
        for (int i = 1; i < comparable.length; i++) {
            if (less(comparable[i], comparable[i - 1])) {
                return false;
            }
        }
        return true;
    }
}

后续陆续的排序方式都会继承这个基类来进行操作;

冒泡排序

一直以来,面试什么的都写过冒泡排序,对于优化冒泡排序也有自己的见解,今天就简单的记录的一下,毕竟这个排序基本在入行都会学习到;

原理

假如现在有一个无序数组n,n[i]与n[i - 1]进行比较,如果n[i - 1] < n[i],那么他们就交换位置,通过这种比较的方式,进行排序,直到遍历完整个数组;

@Override
public void sort(int[] comparable) {
    int len = comparable.length;
    for (int i = 0; i < len; i++) {
        for (int j = 1; j < len; j++) {
            if (less(comparable[j], comparable[j - 1])) {
                exch(comparable, j, j -1);
            }
        }
    }
}

但是大家也发现在这个排序中,效率是很低的,如果是有序数组,代码 还是会进行比较,就执行了很多不必要的代码;

优化

优化上我分为了3点进行优化:
1.判断需要进行排序的数组是否为空;
2.判断数组是否有序;
3.排序过后的组合不需要再次排序;

private void bubbleSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int len = arr.length - 1;
        boolean flag = true; // 如果数组是有序的,就不需要排序
        for (int i = 0; i < len && flag; i++) {
            flag = false;
            for (int j = 0; j < len - i; j++) { // 每次比较后,将最大的数都放到最后,这样就比较len - i次;
                if (less(arr[j + 1], arr[j])) {
                    exch(arr, j, j + 1);
                    flag = true;
                }
            }
        }
    }

结语

我一般都是自己写代码,也没有怎么发表过文章,文笔不太好,希望谅解,如果对于我的代码有异议,或者有更好的写法,欢迎大家对我提出意见,谢谢;

上一篇下一篇

猜你喜欢

热点阅读