冒泡排序
思路：相邻元素进行比较，每一次将最大的元素放到数组最后边，之后进行下一轮重复操作，把最大元素移动到第一次找出的最大元素的前面。
image
重复上图操作N-1次（数组长度为N），但是可以在比较过程中做优化。如下图所示：
image
设置一个flag值，每一次发生交换的时候，都记录交换的位置，下一轮比较只需要比较到上一轮结束后flag的位置。
原因：之后后面元素小于前面元素才发生交换，如果没有发生交换，则代表后方的序列已经是有序的了。
这样做的好处：例如对一个1000个元素的数组排序，后面900个元素已经有序了，如果每一轮都比较到最后，岂不是太浪费时间。所以记录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));
}
}
