【大话数据结构&算法】冒泡排序

短命女 2022-09-25 00:28 193阅读 0赞

起泡排序又称为冒泡排序。它是通过一系列的“交换”动作完成的。首先将第一和第二个记录进行比较，如果第一个记录大于第二个记录，则两者交换位置，否则保持原位置不变；然后比较第二和第三个记录……一直按这种方式比较下去，最终最大的记录被交换到最后，一趟冒泡排序完成。这个过程，大的记录就像一块石头一样“沉底”，小的记录逐渐向上“浮动 ”，冒泡排序的名字也是由此而来的。

**冒泡排序的步骤归纳如下**(以升序排序为例)：

> 1、依次比较序列中相邻的两个元素 ，将较大的放在后面，这样一趟下来 ，最大的元素就被放到了最后；  
> 2、接着重复第一步，第二趟下来， 第二大的元素就被放到倒数第二的位 置上；  
> 3、依次循环，直到最小的元素被放 在第一个位置上，排序结束。

**冒泡排序基本算法实现如下：**

//冒泡排序
    void bubbleSort(int[] a, int n){
        int temp;
        for (int i = 0; i < n; i++) {
              for (int j = 1; j < n - i; j++) {
                    if (a[j-1] > a[j]) {
                         temp = a[j-1];
                         a[j-1] = a[j];
                         a[j] = temp;
                   }
             }
       }
    }

**java代码实现如下：**

public class BubbleSort {
        
    
           public static void main(String[] args) {
                 int[] a = {
       2,5,9,3,0,4,6};
                 bubbleSort(a,7);
                 bubbleSortAdvanced(a,7);
                 for (int i = 0; i < a.length; i++) {
                      System. out.println(a[i]);
                }
                System. out.println("***********" );
                 bubbleSortAdvanced(a,7);
                 for (int i = 0; i < a.length; i++) {
                      System. out.println(a[i]);
                }
    
          }
    
           //原始冒泡排序(注意n的取值)
           public static void bubbleSort(int[] a, int n){
                 int temp;
                 for (int i = 0; i < n; i++) {
                       for (int j = 1; j < n - i; j++) {
                             if (a[j-1] > a[j]) {
                                  temp = a[j-1];
                                  a[j-1] = a[j];
                                  a[j] = temp;
                            }
                      }
                }
          }
    
           /**
           * 冒泡排序优化:
           *
           * 设置一个标志位flag，如果这一趟发生了交换，flag=true，否则flag=false。
           * 如果有一趟没有发生交换，说明排序已经完成。
           *
           * 注意n的取值
           */
           public static void bubbleSortAdvanced(int[] a, int n){
                 int temp;
                 boolean flag = true;
                 while(flag){
                      flag = false;
                       for (int i = 0; i < n; i++) {
                             for (int j = 1; j < n; j++) {
                                   if (a[j-1] > a[j]) {
                                        temp = a[j-1];
                                        a[j-1] = a[j];
                                        a[j] = temp;
                                        flag = true;//如果本趟没有发生数据交换，说明排序已经完成，不再进行比较
                                  }
                            }
                      }
                }
          }      
    }

> **时间复杂度**：
> 
> 最坏情况下，待排序列逆序，此时对于外层循环的每次执行，内层循环中if语句的条件a\[j-1\] > a\[j\]始终成立，即基本操作执行的次数为n-i。i的取值为1 ~ n-1。因此，基本操作总的执行次数为(n-1+1)(n-1)/2=n(n-1)/2，由此可知时间复杂度为**O(n2)\{n的平方\}**。
> 
> 最好情况下，待排序列有序，此时内层循环中if语句的条件始终不成立，交换不发生，且内层循环执行n-1次后整个算法结束，时间复杂度为**O(n)**。
> 
> 综上所述，冒泡排序的平均时间复杂度为**O(n2)\{n的平方\}**。

--------------------

> **空间复杂度**：
> 
> 由算法代码可以看出，额外辅助空间只有一个temp，因此空间复杂度为**0(1)**。