冒泡排序

发表于 更新于 分类于 阅读次数： 本文字数： 3.2k 阅读时长 ≈ 3 分钟
冒泡排序及其优化

冒泡排序

bubble sort 经典的排序算法以及冒泡排序的优化

经典的冒泡排序

两次循环遍历所有的数字，相邻进行交换。是一种稳定的算法，算法的时间复杂度为O(n^2)

优化

image-20200712115306886

第一次优化

第一次优化：优化有序数列排序

对于有序数列，经典的冒泡排序发现不了已经是有序数列，还是会傻傻的一轮一轮进行比较，会浪费很多时间和资源

第二次优化

第二次优化：优化部分有序数列排序

对于部分有序数列，我们可以记录它最后一次交换的位置，从这个位置到数列的末尾，这个区间都是有序的

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
import java.util.Arrays;

/**
 * @Date 2020/7/12 10:17
 * 冒泡排序：
 * 经典的冒泡排序以及冒泡排序的三种优化
 */
public class BubbleSort {
    /**
     * 经典的冒泡排序
     * @param arr
     */
    private static void sort1(int[] arr) {
        int  cycle = 0 ,swap = 0;
        //记录排序次数
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                int temp;
                if(arr[j] > arr[j+1]){
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    swap++;
                }
                cycle ++;
            }
        }
        System.out.println( "循环："+cycle + ",交换：" +swap);
    }

    /**
     * 加了判断优化的冒泡排序
     * @param arr
     */
    private static void sort2(int[] arr){
        //对于已经排序好的数组，经典的冒泡排序还是要从头开始，遍历n次，这样很慢
        int  cycle = 0,swap = 0;
        boolean isSorted;
        for (int i = 0; i < arr.length - 1; i++) {
            isSorted = true;
            //每次重置为true
            for (int j = 0; j < arr.length - 1 - i; j++) {
                int temp;
                if(arr[j] > arr[j+1]){
                    //如果进入这个分支，证明不是有序的队列
                    isSorted = false;
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    swap++;
                }
                cycle ++;
            }
            //如果已经是排序好的数组，立马退出循环
            if(isSorted){
                break;
            }
        }
        System.out.println( "循环："+cycle + ",交换：" +swap);
    }

    /**
     * 对于[3,2,1,4,5,6,7,8]这样的数组，我们会发现，前半部分是无序的，后半部分是有序的
     * 会有很多无意义的判断
     * 我们需要对 数列有序区 进行判断：
     *    记录最后一次元素交换的位置，这个位置就是有序数列的边界，从这到数组末尾，都是有序的
     * @param arr
     */
    private static void sort3(int[] arr){
        int  cycle = 0 , swap = 0;
        int lastEchangeIndex = 0;
        // 记录最后一次交换位置的下标
        boolean isSorted;
        int sortBorder = arr.length - 1;
        //排序的边界
        for (int i = 0; i < arr.length - 1; i++) {
            isSorted = true;
            //每次重置为true
            for (int j = 0; j < sortBorder; j++) {
                int temp;
                if(arr[j] > arr[j+1]){
                    //如果进入这个分支，证明不是有序的队列
                    isSorted = false;
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    //记录最后一次排序位置
                    lastEchangeIndex = j;
                    swap++;
                }
                cycle ++;
            }
            sortBorder = lastEchangeIndex;
            //如果已经是排序好的数组，立马退出循环
            if(isSorted){
                break;
            }
        }
        System.out.println( "循环："+cycle + ",交换：" +swap);
    }

    public static void main(String[] args) {
        // 给出四种数组情况 ： 无序、有序、逆序、部分有序
        System.out.println("------无序数组三种排序对比-------");
        arr1 = new int[]{5, 8, 6, 3, 9, 2, 1, 7};
        sort1(arr1);

        arr1 = new int[]{5, 8, 6, 3, 9, 2, 1, 7};
        sort2(arr1);

        arr1 = new int[]{5, 8, 6, 3, 9, 2, 1, 7};
        sort3(arr1);

        System.out.println("------有序数组三种排序对比-------");
        arr2 = new int[]{1,2,3,4,5,6,7,8};
        sort1(arr2);

        arr2 = new int[]{1,2,3,4,5,6,7,8};
        sort2(arr2);

        arr2 = new int[]{1,2,3,4,5,6,7,8};
        sort3(arr2);

        System.out.println("------逆序数组三种排序对比-------");
        arr3 = new int[]{9,8,7,6,5,4,3,2};
        sort1(arr3);

        arr3 = new int[]{9,8,7,6,5,4,3,2};
        sort2(arr3);

        arr3 = new int[]{9,8,7,6,5,4,3,2};
        sort3(arr3);

        System.out.println("------部分有序数组三种排序对比-------");
        arr4 = new int[]{3,2,1,4,5,6,7,8};
        sort1(arr4);

        arr4 = new int[]{3,2,1,4,5,6,7,8};
        sort2(arr4);

        arr4 = new int[]{3,2,1,4,5,6,7,8};
        sort3(arr4);


    }
}

运行结果：

image-20200712112515663