[数据结构与算法]冒泡排序Java

冒泡排序

一次比较两个元素，如果它们的顺序错误就将它们交换过来。每一趟遍历均能将待排序的元素中的最大数找出，并排到正确的位置。

1.

package sort;

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = new int[]{3,5,23,54};
        BubbleSort(arr);
        for (int i = 0;i < arr.length;i++) {
            System.out.println(arr[i]);
        }
    }
    public static int[] BubbleSort(int[] arr) {
        for (int i = 0;i < arr.length-1;i++) {
            for (int j = 0;j < arr.length-i-1;j++) {
                if (arr[j] > arr[j+1]) {
                    swap(arr[j],arr[j+1]);
                }
            }
        }
        return arr;
    }
    public static void swap(int a,int b) {
        int tmp = a;
        a = b;
        b = tmp;
    }
}

2.

package sort;

import java.util.Arrays;

public class BubbleSort02 {
    public static void main(String[] args) {
        Integer[] array = new Integer[]{1,23,4,24};
        sort2(array);
        System.out.println(Arrays.toString(array));
    }
    public static void sort2(Comparable[] arr) {
        for (int i = arr.length-1; i > 0;i--) {
            for (int j = 0; j < i;j++) {
                if (compare(arr[j],arr[j+1])) {
                    swap(arr,j,j+1);
                }
            }
        }
    }
    public static boolean compare(Comparable o1,Comparable o2) {
        if (o1.compareTo(o2) > 0) {
            return true;
        } else {
            return false;
        }
    }

    public static void swap(Comparable[] arr,int a,int b) {
        Comparable tmp;
        tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }
}

时间复杂度分析

冒泡排序采用双层for循环，其中内层循环的循环体是真正完成排序的代码，因此分析内层循环体的执行次数即可。
在最坏情况下，即数组中所有元素都为逆序：
	元素的比较次数为：(n-1)+(n-2)+...+2+1= (n*(n-1))/2
	元素的交换次数为：(n-1)+(n-2)+...+2+1= (n*(n-1))/2
	总执行次数为：(n*(n-1))/2+(n*(n-1))/2=n*(n-1)
因此时间复杂度为：O(n^2)

空间复杂度分析

空间复杂度为交换元素是临时变量所占用的内存空间。
最差的空间复杂度为：O(n)