我想知道我如何能够优化泡沫排序,以便忽略已经排序的元素,即使在第一次通过之后.
Eg. [4,2,3,1,5,6] --> [2,**4,6**]
我们观察到[4,6]已经排序顺序,怎么修改我的代码,以便在下一遍中忽略这3个元素？ (这意味着排序会更有效率吗？)
你建议一种递归方法吗？
public static void bubblesort(int[] a) {
for(int i=1; i<a.length; i++) {
boolean is_sorted = true;
for(int j=0; j<a.length; j++) {
if(a[j] > a[j+1]) {
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
is_sorted = false;
}
}
if(is_sorted) return;
}
}
谢谢你的时间！
解决方法
首先,你有一个超出范围的访问权限：
for(int j=0; j<a.length; j++) {
if(a[j] > a[j+1]) {
对于j == a.length-1,所以循环条件应该是j<则为a.length-1. 但是,在Bubble排序中,你知道在k遍之后,最大的k个元素被排列在数组的k个最后的条目中,所以常规的Bubble排序使用
public static void bubblesort(int[] a) {
for(int i=1; i<a.length; i++) {
boolean is_sorted = true;
for(int j=0; j < a.length - i; j++) { // skip the already sorted largest elements
if(a[j] > a[j+1]) {
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
is_sorted = false;
}
}
if(is_sorted) return;
}
}
现在,当数组具有最大元素的长排序尾部时,仍然会执行大量不必要的迭代,例如,将k,k-1,…,1作为第一个k个元素,并按顺序排列为k 1到100000000那.标准的气泡排序将通过(几乎)整个数组通过k次.
但是,如果你记得你最后一次交换的位置,那么你知道在这个索引之后,依次是最大的元素
public static void bubblesort(int[] a) {
int lastSwap = a.length-1;
for(int i=1; i<a.length; i++) {
boolean is_sorted = true;
int currentSwap = -1;
for(int j=0; j < lastSwap; j++) {
if(a[j] > a[j+1]) {
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
is_sorted = false;
currentSwap = j;
}
}
if(is_sorted) return;
lastSwap = currentSwap;
}
}
将对上述示例进行排序,只有一次遍历整个数组,剩余的只通过(短)前缀.
当然,一般来说,这不会买你多少,但是然后优化泡沫排序是一个相当徒劳的运动.