经典算法--冒泡排序再优化

发表于 | 分类于

冒泡排序的原理

比较相邻元素的大小并将大的元素向后移，每执行一次，都会将一个大的元素放到后面，如此循环多次。代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//经典模式
public void bubbleSort(int[] array){
        int len = array.length;
        int temp;
        for (int i = 0;i < len - 1;i++){
            for (int j = 0; j < len -1 - i; j++){
                if (array[j] > array[j+1]){
                    temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
        }
    }

两种优化方式

优化的方式主要是减少交换次数，

  • 利用标志位减少查找顺序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//优化之后的冒泡排序
   private void bubbleSort2 (int[] array){
       int len = array.length;
       int temp;
       boolean change;
       for (int i = 0;i < len -1;i++){
           change = false;
           for (int j = 0; j < len -1 - i;j++){
               if (array[j] > array[j+1]){
                   temp = array[j];
                   array[j] = array[j+1];
                   array[j+1] = temp;
                   change = true;
               }
           }
           if (!change) break;
       }
   }
  • 利用标志位和记录最后一次交换的位置的方法来进行优化 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*
 * 冒泡排序算法 优化1：带有标志位的：，一旦不交換即array[j]<array[j-1]不存在，则表明已经排序完成，不用再循环
 * 优化2：记录最后一次交换发生的位置，该位置之前的地方都已经表示排完序了。这里是前向冒泡法。
 */
public void bubbleSort(int[] array){
    boolean flag = true;
    int lastExchangeIndex = 0;
    int len = array.length;
    while (flag) {
        flag = false;
        for(int i = lastExchangeIndex; i < len;i++){
            for (int j = len - 1;j > i;j--){
                if (array[j] < array[j - 1]){
                    array[j] ^= array[j -1];
                    array[j - 1] ^= array[j];
                    array[j] ^= array[j -1];
                    flag = true;
                    lastExchangeIndex = j -1;
                }
            }
        }
    }
}
  • 双向扫描，解决不对称问题
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
//双向扫描，解决不对称问题
   public void acvanceBubbleSort(int[] array){
       int low = 0;
       int high = array.length - 1;
       int index = low;
       boolean flag = true;
       while (high > low && flag){
           flag = false;
           for (int i = low;i < high;i++){
               if (array[i] > array[i + 1]){
                   array[i] ^= array[i +1];
                   array[i + 1] ^= array[i];
                   array[i] ^= array[i+1];
                   index = i;
                   flag = true;
               }
           }
           high = index;
           for(int i = high; i > low;i--){
               if (array[i] < array[i -1]){
                   array[i] ^= array[i -1];
                   array[i -1] ^= array[i];
                   array[i] ^= array[i -1];
                   index = i;
                   flag = true;
               }
           }
           low = index;
       }
   }

下面是一些测试两个数组的一些数据，

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
int[] arr1 = new int[800];
        for (int i = 0;i < arr1.length;i++){
            arr1[i] = new Random().nextInt(800) + 1;
        }
        int[] arr2 = new int[800];
        for (int i = 0;i < arr2.length;i++){
            arr2[i] = new Random().nextInt(800) + 1;
        }
        int[] arr3 = new int[800];
        for (int i = 0;i < arr3.length;i++){
            arr3[i] = new Random().nextInt(800) + 1;
        }
        int[] arr4 = new int[800];
        for (int i = 0;i < arr4.length;i++){
            arr4[i] = new Random().nextInt(800) + 1;
        }
        long now = System.currentTimeMillis();
        bubbleSort(arr1);
        long m = System.currentTimeMillis();
        Log.d("main","冒泡排序耗时:" + (m - now) + "ms");
        long a = System.currentTimeMillis();
        bubbleSort2(arr2);
        long b = System.currentTimeMillis();
        Log.d("main","冒泡排序优化后1：" + (b - a) + "ms");
        long a3 = System.currentTimeMillis();
        bubbleSort3(arr3);
        long b3 = System.currentTimeMillis();
        Log.d("main","冒泡排序优化后2：" + (b3 - a3) + "ms");
//
        long a4 = System.currentTimeMillis();
        acvanceBubbleSort(arr4);
        long b4 = System.currentTimeMillis();
        Log.d("main","冒泡排序优化后2：" + (b4 - a4) + "ms");
//****************************************************************//
04-25 22:48:39.512 1380-1380/com.ambition521.list D/main: 冒泡排序耗时:65ms
04-25 22:48:39.582 1380-1380/com.ambition521.list D/main: 冒泡排序优化后1：62ms
04-25 22:48:39.652 1380-1380/com.ambition521.list D/main: 冒泡排序优化后2：77ms
04-25 22:48:39.732 1380-1380/com.ambition521.list D/main: 冒泡排序优化后2：80ms
04-25 22:49:01.922 1380-1380/com.ambition521.list D/main: 冒泡排序耗时:12ms
04-25 22:49:01.932 1380-1380/com.ambition521.list D/main: 冒泡排序优化后1：11ms
04-25 22:49:01.942 1380-1380/com.ambition521.list D/main: 冒泡排序优化后2：13ms
04-25 22:49:01.962 1380-1380/com.ambition521.list D/main: 冒泡排序优化后2：13ms
04-25 22:49:08.322 1380-1380/com.ambition521.list D/main: 冒泡排序耗时:11ms
04-25 22:49:08.352 1380-1380/com.ambition521.list D/main: 冒泡排序优化后1：22ms
04-25 22:49:08.362 1380-1380/com.ambition521.list D/main: 冒泡排序优化后2：16ms
04-25 22:49:08.372 1380-1380/com.ambition521.list D/main: 冒泡排序优化后2：11ms
04-25 22:49:15.322 1380-1380/com.ambition521.list D/main: 冒泡排序耗时:11ms
04-25 22:49:15.332 1380-1380/com.ambition521.list D/main: 冒泡排序优化后1：9ms
04-25 22:49:15.342 1380-1380/com.ambition521.list D/main: 冒泡排序优化后2：12ms
04-25 22:49:15.352 1380-1380/com.ambition521.list D/main: 冒泡排序优化后2：13ms
04-25 22:49:29.122 1380-1380/com.ambition521.list D/main: 冒泡排序耗时:11ms
04-25 22:49:29.132 1380-1380/com.ambition521.list D/main: 冒泡排序优化后1：11ms
04-25 22:49:29.152 1380-1380/com.ambition521.list D/main: 冒泡排序优化后2：19ms
04-25 22:49:29.162 1380-1380/com.ambition521.list D/main: 冒泡排序优化后2：10ms
04-25 22:49:33.992 1380-1380/com.ambition521.list D/main: 冒泡排序耗时:9ms
04-25 22:49:34.002 1380-1380/com.ambition521.list D/main: 冒泡排序优化后1：8ms
04-25 22:49:34.012 1380-1380/com.ambition521.list D/main: 冒泡排序优化后2：11ms
04-25 22:49:34.032 1380-1380/com.ambition521.list D/main: 冒泡排序优化后2：16ms

总结一下，当我们选取适当方法的时候还是应该根据数据源做相应的处理。

在上面的比较中，有不妥的地方，不应该用不同的数组去针对不同的方法进行比较，但是效果还是可以看见的。