冒泡排序
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;
}
}
}
}
结语
我一般都是自己写代码,也没有怎么发表过文章,文笔不太好,希望谅解,如果对于我的代码有异议,或者有更好的写法,欢迎大家对我提出意见,谢谢;