[数据结构与算法]排序算法-交换排序-冒泡排序

排序算法-交换排序-冒泡排序

基于“交换”的排序：根据序列中两个元素的关键字的比较结果来对换这两个记录在序列中的位置。

算法思想：

从后往前（或者从前往后）两两比较相邻元素的值，若为逆序，则交换他们，如果两个元素相同的话，并不交换他们的位置，这样可以保证算法的稳定性，直到序列比较完毕。这样的过程为“一趟”冒泡排序。

首先第一个关键字和第二个关键字进行比较，如果第一个大，则两者交换，否则不交换；然后第二个关键字与第三个关键字进行比较，如果第二个大，则两者交换，否则不交换…。一直按照这种方式进行下去，最终最大的那个关键字被交换到了最后，一趟冒泡完成。经过n-1趟冒泡，最终整个使得整个序列有序。整个过程中，大的关键字像“沉底”，小的关键字像“气泡“”一样向上“浮动”。

每一趟排序之后都会使一个元素移动到最终位置，已经确定最终位置的元素在之后的处理中无须再对比。

代码：

public static void main(String[] args) {
        int[] nums = {3,8,4,5,6,8,9,0,1};
        bubblesort2(nums,nums.length);
        for(int num:nums){
            System.out.print(num);
        }
    }
    public static void bubblesort(int[] nums, int n){
        for(int i=n-1;i>0;--i){        //总共n个数，需要n-1趟冒泡
            for(int j=0;j<i;++j){         // 每次对未排好序的关键字进行冒泡，此处代码为将较大关键字下沉到数组末尾，
                if(nums[j]>nums[j+1]){    // 每经过一次冒泡排序都会有一个关键字放到最终的位置
                    int temp = nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = temp;
                }
            }
        }
    }

如果某一趟排序过程中未发生交换，说明序列已经有序，则算法可以提前结束。

代码

public static void bubblesort2(int[] nums, int n){
        for(int i=n-1;i>0;--i){           //总共n个数，需要n-1趟冒泡
            boolean flag = false;         // 判断本次冒泡是否有序的变量，如果数组已经有序，则提前退出。
            for(int j=0;j<i;++j){         // 每次对未排好序的关键字进行冒泡，此处代码为将较大关键字下沉到数组末尾，
                if(nums[j]>nums[j+1]){    // 每经过一次冒泡排序都会有一个关键字放到最终的位置
                    int temp = nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = temp;
                    flag = true;
                }
            }
            if(!flag) break;             // 判断本次冒泡是否有序，如果数组已经有序，则提前退出。
        }
    }

时间复杂度：（Bubble sort 2）

1. 最好情况：待排序序列有序，此时内层循环中if语句的条件始终不成立，交换不发生，且内层循环执行$n?1$次后整个算法结束，时间复杂度为$O(n)$.
2. 最坏情况：待排序序列逆序，此时对于外层循环的每次执行，内层循环中的if语句始终成立，内层循环中的关键字交换与对比需要执行$n?i$次。i的取值为$1至n?1$。因此总共的交换（对比）次数为$(n?1+1)(n?1)/2=n(n?1)/2$, 时间复杂度为$O(n^2).$

平均时间复杂度为$O(n^2)$

空间复杂度：O(1).

算法稳定性：稳定