基础数据结构——用递归完成冒泡排序

冒泡排序

冒泡排序就是通过第一个元素依次与后面的元素进行比较，如果第一个元素比第二个元素大，那我们进行两个元素的交换，再调用这个交换函数，完成递归冒泡排序

如上完成了一轮冒泡排序，我们来根据思路完成代码。

private static void bubble1(int[]a,int j){
        if(j==0){
            return;
        }
        for(int i=0;i<j;i++){
            if(a[i]>a[i+1]){
                int temp = a[i];
                a[i] = a[i+1];
                a[i+1] = temp;
            }
        }
        bubble1(a,j-1);
    }

在上述代码中，我们传入两个参数，一个数组一个末尾指针。

我们进入迭代比较，每完成一次交换循环，开始继续调用，当末尾指针指向0索引的时候终止调用。

我们来思考一个问题，如果在完全遍历结束之前，数组就已经按照顺序排序的话，我们是不是可以提前返回数组呢，而不是继续循环到结束

我们只需要设置一个新的值x初值为0，如果发生了交换操作，就将该x赋值为当前的i（发生交换的索引）

我们来看代码：

private static void bubble(int[]a,int j){
        if(j==0){
            return;
        }
        int x=0;
        for(int i=0;i<j;i++){
            if(a[i]>a[i+1]){
                int temp = a[i];
                a[i] = a[i+1];
                a[i+1] = temp;
                x=i;
            }
        }
        bubble(a,x);
    }

    public static void sort(int[] a){
        bubble(a,a.length-1);
    }

并且实现了一个sort方法，便于用户调用