冒泡排序(BubbleSort)

执行流程
  • 依次比较两个相邻元素如果前者比后者大，交换两者
  • 一轮比较完毕，则最后一个元素为最大者
  • 再进行第二轮比较，直到末尾
冒泡排序一

代码如下:

 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

    /*
    * 交换，array i 和 j位置的元素
    * */
    protected void swap(int i1, int i2){
        int tmp = array[i1];
        array[i1] = array[i2];
        array[i2] = tmp;
    }

    /*
    * 比较两个下标的元素
    * 返回值等于0 , 代表array[i1] == array[i2]
    * 返回值 < 0,  代表array[i1] < array[i2]
    * 返回值 > 0,  代表array[i1] > array[i2]
    * */
    protected int cmp(int i1, int i2){
        return array[i1] - array[i2];
    }   

		protected void sort() {

        for (int i = array.length - 1; i >= 0; i--) {
            for (int j = 0; j < i; j++) {
                if (cmp(j, j+1) > 0){
                    swap(j, j+1);
                }
            }
        }
    }
优化一：

在全排序时，提前退出循环，不再遍历。

此中优化只对排序过程中提前全排序时，优化循环次数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

		protected void sort() {
				// 全排序时，则不再遍历
        for (int i = array.length - 1; i >= 0; i--) {
          	boolean sorted = true;
            for (int j = 0; j < i; j++) {
                if (cmp(j, j+1) > 0){
                    swap(j, j+1);
                  
                  	sorted = false;
                }
            }
          	if(sorted) break;
        }
    }
优化二：
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

		protected void sort() {
        // 优化
        // 记录交换位置
        // 局部交换时，后边的有序了，后边的不再比较
        for (int i = array.length - 1; i >= 0; i--) {
            // 当完全有序时，一轮扫描结束
            int sortedIdx = 0;
            for (int j = 0; j < i; j++) {
                if (cmp(j, j+1) > 0){
                    swap(j, j+1);

                    sortedIdx = j + 1;
                }
            }
            i = sortedIdx;
        }
    }