针对基本有序数列的改良冒泡排序

我把这个排序称为OooooSort

hahahaha虽然没有Java自带的TimSort高效,但也只是稍稍逊色,这是一个闲暇时做的小玩意~可以叫做双向冒泡法,或者改良冒泡法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
* 双向冒泡,不需要额外存储空间,速度稍慢于tim sort
* @author zrj CreateDate: 2019/8/4
*/
public class OooooSort {

public static <E> void sort(ArrayList<E> list, Comparator<E> comparator) {
if(list == null || list.size() == 0) {
return;
}

int maxSorted = 0;
boolean hasSwap;
E last;
int j = 0;
do {
hasSwap = false;
last = list.get(maxSorted);
for(int i = 1; i < list.size() - j; i ++ ){
E cur = list.get(i);
if(comparator.compare(last, cur) > 0) {
hasSwap = true;
list.set(i - 1, cur);
list.set(i, last);
E innerLast = list.get(i - 1);
for(int k = i - 2; k >=0; k--) {
E innerCur = list.get(k);
if(comparator.compare(innerCur, innerLast) > 0) {
list.set(k + 1, innerCur);
list.set(k, innerLast);
} else {
break;
}
}
} else {
if(!hasSwap) {
maxSorted = i;
}
last = cur;
}
}
j++;
} while (maxSorted < list.size() && hasSwap);
}
}

对于基本有序的数列,快排的效率是非常低的,相对来说,冒泡的潜力要更高一些,但是冒泡做了很多无用的工作,所以我稍稍改进了一下,每次冒一次泡后,都回头对刚刚换下去的数据进行一下反向冒泡(沉底),这样,每次向上冒一次泡之后,身后的数据都已经是全局有序的了,还有一个优化点,冒泡的时候可以记录下最长未发生交换的位置,应为没有发生过交换,所以这批数据是已经有序的,上面的代码中maxSorted就是用来干这个的,这样下轮冒泡就减少了很多工作。

如果数据基本有序,效率可以逼近O(n),突破排序的算法理论极限了有木有,好了当然不是,算法理论极限是通用情况,这里是基本有序。

但是Java提供的TimSort性能更加优秀。