冒泡排序
思路：相鄰元素進(jìn)行比較欢搜，每一次將最大的元素放到數(shù)組最后邊缕碎，之后進(jìn)行下一輪重復(fù)操作切心，把最大元素移動(dòng)到第一次找出的最大元素的前面鹏氧。
image
重復(fù)上圖操作N-1次（數(shù)組長(zhǎng)度為N）渤涌，但是可以在比較過(guò)程中做優(yōu)化。如下圖所示：
image
設(shè)置一個(gè)flag值把还，每一次發(fā)生交換的時(shí)候实蓬，都記錄交換的位置，下一輪比較只需要比較到上一輪結(jié)束后flag的位置吊履。
原因：之后后面元素小于前面元素才發(fā)生交換安皱，如果沒(méi)有發(fā)生交換，則代表后方的序列已經(jīng)是有序的了艇炎。
這樣做的好處：例如對(duì)一個(gè)1000個(gè)元素的數(shù)組排序酌伊，后面900個(gè)元素已經(jīng)有序了，如果每一輪都比較到最后缀踪，豈不是太浪費(fèi)時(shí)間悉默。所以記錄flag值鹅龄，只比較到最后一次交換的位置即可躏哩。
下面是完整代碼：
public class BubbleSort {
public static <T> void bubbleSort(T[] arr, Comparator<T> comparator){
int flag = arr.length;
while(flag > 0){
int end = flag;
flag = 0;
for(int i = 1; i < end; i++){
if(comparator.compare(arr[i-1], arr[i]) > 0){
T temp = arr[i];
arr[i] = arr[i-1];
arr[i-1] = temp;
flag = i;
}
}
}
}
public static void main(String[] args) {
Integer arr[] = {10,50,24,11,68,20,41,0,24,25,4,7,94,15,5,44,66};
BubbleSort.bubbleSort(arr, new IntegerComparator());
System.out.println(Arrays.toString(arr));
}
}
