冒泡排序优化

普通的冒泡排序相信大家信手拈来,不在赘述!

第一版

public class BubbleSort {
    public static void main(String[] args) {
        int[] ARRAY = {5,8,6,3,9,2,1,7};
        sort(ARRAY);
        System.out.println(Arrays.toString(ARRAY));
    }
    public static void sort(int[] array) {
        int temp=0; //临时变量
        for (int i = 0; i < array.length-1; i++) {
            for (int j = 0; j < array.length - 1 -i; j++) { //比较的次数
                if (array[j + 1] < array[j]) {
                    temp = array[j + 1];
                    array[j + 1] = array[j];
                    array[j] = temp;
                }
            }
        }
    }
}

时间复杂度 对于上面12个数据项,从第一个元素开始,第一趟比较了11次,第二趟比较了10次,依次类推,一直到最后一趟,就是:

11 + 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 66次 若有n个元素,则第一趟比较为(n-1)次,第二趟比较为(n-2)次,依次类推:

(n-1) + (n-2) + (n-3) + …+ 2 + 1 = n * (n-1)/2 在大O表示法中,去掉常数系数和低阶项,该排序方式的时间复杂度为:O(n2)

算法稳定性 假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的;否则称为不稳定的。——百度百科

在代码中可以看到,array[j + 1] = array[j]的时候,我们可以不移动array[i]和array[j],所以冒泡排序是稳定的。

第二版

原始的冒泡排序有哪些优化点呢?

让我们回顾一下刚才描述的排序细节,仍然以5,8,6,3,9,2,1,7这个数列为例,当排序算法分别执行到第六、第七、第八轮的时候,

很明显可以看出,自从经过第六轮排序,整个数列已然是有序的了。可是我们的排序算法仍然“兢兢业业”地继续执行第七轮、第八轮。

这种情况下,如果我们能判断出数列已经有序,并且做出标记,剩下的几轮排序就可以不必执行,提早结束工作。

public class BubbleSort {
    public static void main(String[] args) {
        int[] ARRAY = {24, 7, 43, 78, 62, 98, 82, 18, 54, 37, 73, 9};
        sort(ARRAY);
        System.out.println(Arrays.toString(ARRAY));
    }
    public static void sort(int[] array) {
        for (int i = 0; i < array.length-1; i++) {
            boolean flag=false;//标识变量,是否进行过交换
            for (int j = 0; j < array.length - 1 -i; j++) {
                if (array[j + 1] < array[j]) {
                    int temp = array[j + 1];
                    array[j + 1] = array[j];
                    array[j] = temp;
                    //有元素交换,所以不是有序,标记变为false
                    flag=true;
                }
            }
            if (!flag) break;
	    //System.out.println(Arrays.toString(array));//作为展示用,看看打印了几轮
        }
    }
}

这一版代码做了小小的改动,利用布尔变量isSorted作为标记。如果在本轮排序中,元素有交换,则说明数列无序;如果没有元素交换,说明数列已然有序,直接跳出大循环。

第三版

这个数列的特点是前半部分(3,4,2,1)无序,后半部分(5,6,7,8)升序,并且后半部分的元素已经是数列最大值。

按照现有的逻辑,有序区的长度和排序的轮数是相等的。比如第一轮排序过后的有序区长度是1,第二轮排序过后的有序区长度是2 ……

实际上,数列真正的有序区可能会大于这个长度,比如例子中仅仅第二轮,后面5个元素实际都已经属于有序区。因此后面的许多次元素比较是没有意义的。

如何避免这种情况呢?我们可以在每一轮排序的最后,记录下最后一次元素交换的位置,那个位置也就是无序数列的边界,再往后就是有序区了。

//优化 -有序区========================================================
public class BubbleSort {
    public static void main(String[] args) {
        int[] ARRAY = {24, 7, 43, 78, 62, 8, 8, 18, 54, 79, 173, 239};
				sort(ARRAY);
        System.out.println(Arrays.toString(ARRAY));
    }
    public static void sort(int[] array) {
        //记录最后一次交换的位置
        int lastExchangeIndex=0;
        //无序数列的边界,每次只要比到这里即可
        int sortBorder=array.length-1;

        for (int i = 0; i < array.length-1; i++) {
            boolean flag=false;//标识变量,是否进行过交换
            for (int j = 0; j < sortBorder; j++) {
                if (array[j + 1] < array[j]) {
                    int temp = array[j + 1];
                    array[j + 1] = array[j];
                    array[j] = temp;
                    //有元素交换,所以不是有序,标记变为false
                    flag=true;
                    //把无序数列的边界更新为最后一次交换元素的位置
                    lastExchangeIndex=j;
                }
            }
						sortBorder=lastExchangeIndex;
            if (!flag) break;
            System.out.println("第"+(i+1)+"次:"+Arrays.toString(array));//作为展示用
        }
    }
}

第四版

冒泡排序的每一个元素都可以像小气泡一样,根据自身大小,一点一点向着数组的一侧移动。算法的每一轮从都是从左到右比较元素,进行单向的位置交换

那么鸡尾酒排序做了怎样的优化呢?

鸡尾酒排序的元素比较和交换过程是双向的。

鸡尾酒(双向冒泡)排序算法基本过程

(1)先对数组从左到右进行冒泡排序(升序),则最大的元素去到最右端;

(2)再对数组从右到左进行冒泡排序(降序),则最小的元素去到最左端;

以此类推,依次改变冒泡的方向,并不断缩小未排序元素的范围,直到最后一个元素结束.

排序过程就像钟摆一样,第一轮从左到右,第二轮从右到左,第三轮再从左到右……

//冒泡之鸡尾酒排序=====================================================
public class BubbleSort {
    public static void main(String[] args) {
        int[] ARRAY = {2,3,4,5,6,7,8,1};
				sort(ARRAY);
        System.out.println(Arrays.toString(ARRAY));
    }
    public static void sort(int[] array) {
        int temp=0;
        for (int i = 0; i < array.length/2; i++) {
            boolean flag=false;//标识变量,是否进行过交换
            //奇数轮,从左向右比较和交换
            for (int j = i; j < array.length-1-i; j++) {
                if (array[j + 1] < array[j]) {
                    temp = array[j + 1];
                    array[j + 1] = array[j];
                    array[j] = temp;
                    //有元素交换,所以不是有序,标记变为false
                    flag=true;
                    //把无序数列的边界更新为最后一次交换元素的位置
                }
            }
            System.out.println("第"+(i+1)+"次:"+Arrays.toString(array));//作为展示用 避坑 不要写成i++ 
            if (!flag) break;

            //偶数轮之前,重新标记为false
            flag=false;
            //偶数轮 从右向左比较和交换
            for (int j = array.length-1-i; j > i; j--) {
                if(array[j]<array[j-1]){
                    temp=array[j];
                    array[j]=array[j-1];
                    array[j-1]=temp;
                    //有元素交换,不是有序,flag设置为true
                    flag=true;
                }
            }
            System.out.println("第"+(i+1)+"次:"+Arrays.toString(array));//作为展示用
            if (!flag) break;

        }
    }
}

最后,附上下图:

  • 打赏
请选择打赏方式
  • 微信
  • 支付宝
订阅评论
提醒
0 评论
内联反馈
查看所有评论
0
动动你可爱的小手留下个评论吧x