简单排序算法---- 冒泡排序

冒泡排序

1. 冒泡排序(Bubble Sort)

• 冒泡排序:
  • 通过比较相邻两个元素的大小,若需要从小到大排序,且前一个元素比后一个元素大,就交换这两个元素的位置 ;
  • 对每对相邻的元素做同样的工作,从开始的一对元素到结尾的最后一对元素.最终最后位置的元素就是最大值.

例如对 Integer[] arr = {4,2,5,3,1}进行排序.

冒泡次数	冒泡后的结果
初始状态	{ 4, 2, 5, 3, 1 }
第一次	{ 2, 4, 3, 1, 5}
第二次	{ 2, 3, 1, 4, 5 }
第三次	{ 2, 1, 3, 4, 5 }
第四次	{ 1, 2, 3, 4, 5 }

java代码示例:

public static void main(String[] args) {
        int[] arr = {4, 2, 5, 3, 1};
        bubbleSort(arr);
        System.out.println(Arrays.toString(arr));
        //打印输出 [1, 2, 3, 4, 5]
    }

    public static int[] bubbleSort(int[] arr) {
        for (int i = arr.length - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[j + 1]) {
                    //定义临时变量,交换元素位置
                    int tem = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tem;
                }
            }
        }
        return arr;
    }

时间复杂度分析

• 冒泡排使用了双层for循环,在最坏的情况下, 也就是arr = {5,4,3,2,1}时,需要排序的次数为:

​ ((N-1)+1)*(N-1)/2 = N^2/2-N/2 = N^2 - N;也就是说冒泡排序的时间复杂度为O(N^2);