算法思路

  1. 比较相邻的元素。如果第一个比第二个大,就交换它们两个;
  2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数;
  3. 针对所有的元素重复以上的步骤,除了最后一个;
  4. 重复步骤1~3,直到排序完成。 冒泡排序

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
     * 冒泡排序
     *
     * @param array
     * @return
     */
    public class BubbleSort {

    public static void sort(int array[])
    {
        int tmp  = 0;
        for(int i = 0; i < array.length; i++)
        {
            //有序标记,每一轮的初始是true
            boolean isSorted = true;

            for(int j = 0; j < array.length-1-i; j++)
            {
                if(array[j] > array[j+1])
                {
                    tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                    //有元素交换,所以不是有序,标记变为false
                    isSorted = false;
                     
                }
            }
            if(isSorted){
                break;
            }
        }
    }

    public static void main(String[] args){
        int[] array = new int[]{3,4,2,1,5,6,7,8};
        sort(array);
        System.out.println(Arrays.toString(array));
    }
}

算法分析

最佳情况:T(n) = O(n) 最差情况:T(n) = O(n^2) 平均情况:T(n) = O(n^2)

参考文章:https://www.cnblogs.com/guoyaohua/p/8600214.html