数据结构与算法-冒泡排序

谁借莪１个温暖的怀抱￠ 2022-04-06 02:40 256阅读 0赞

### 概览 ###

*   *   *   *  基本概念
             *  java代码实现
             *  图示执行过程
             *  进一步优化
             *  时间复杂度分析

#### 基本概念 ####

> 冒泡排序（Bubble Sort）一种交换排序，它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。

#### java代码实现 ####

//声明待排序数组
    int[] a = {
        9,1,5,8,3,7,4,6,2};
    for (int i = 0; i < a.length; i++) {
        
        for (int j = a.length-1; j > i; j--) {
         /* 注意j是从后往前循环 */
     	   if (a[j-1] > a[j]) {
         /* 若前者大于后者，交换之 */
    	      int temp = a[j-1];
    	      a[j-1] = a[j];
    	      a[j] = temp;
    	   }
         }
    }

#### 图示执行过程 ####

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70][]

#### 进一步优化 ####

*  如果我们待排序的序列是\{2,1,3,4,5,6,7,8,9\}，也就是说，除了第一和第二的关键字需要交换外，别的都已经是正常的顺序。当i=1时，交换了2和1，此时序列已经有序，但是算法仍然不依不饶地将i=2到9以及每个循环中j循环都执行一遍，尽管并没有交换数据，但是之后的大量比较还是大大地多余了。![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70 1][]
 *  设置flag标记，及时退出循环

//申明待排序数组
    int[] a = {
        9,1,5,8,3,7,4,6,2};
    boolean flag = true;	/* flag用来作为标记 */
    for (int i = 0; i < a.length && flag; i++) {
         /* 若flag为false则退出循环 */
    	flag = false; /* 初始为false */
    	for (int j = a.length-1; j > i; j--) {
        
     		if (a[j-1] > a[j]) {
        
    			int temp = a[j-1];
    			a[j-1] = a[j];
    			a[j] = temp;
    			flag = true; /* 如果有数据交换，则flag为true */
    		}
     	}
    }

#### 时间复杂度分析 ####

*  最好的情况，也就是待排序的表本身就是有序的，那么根据优化后的代码可以推断出就是n-1次比较，没有数据交换，时间复杂度为O(n)；
 *  最坏的情况，也就是待排序表是逆序的，此时需要比较1+2+3+···+(n-1) = n(n-1)/2次，并作等数量级的记录移动，时间复杂度为O(n2)；
 *  因此，总的时间复杂度为O(n2)。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70]: /images/20220406/6c8ed046e45b48f8991fd6a20a0d51fb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZURF9TTA_size_16_color_FFFFFF_t_70 1]: /images/20220406/50dfd764e6454542aa03f274077ead8c.png