一、 算法简介

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

二、算法步骤

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

三、算法动态图

四、代码实现

1. C++

   void BubbleSort(std::vector<int> &arr)
   {
       bool flag = true;
       for (int i = 1; i < arr.size() && flag; i++)
       {
           flag = false;
           for (int j = arr.size() - 1; j >= i; j--)
           {
               std::cout << "pre" << arr[j] << " " << arr[j - 1] << std::endl;
               if (arr[j - 1] > arr[j])
               {
                   std::swap(arr[j - 1], arr[j]);
                   flag = true;
               }
               std::cout << "end:" << arr[j] << " " << arr[j - 1] << std::endl;
           }
           std::cout << "" << std::endl;
       }
   }
   
   void BubbleSort_1(std::vector<int> &arr)
   {
       bool flag = true;
       for (int i = arr.size() - 1; i >= 0 && flag; i--)
       {
           flag = false;
           for (int j = 0; j < i; j++)
           {
               std::cout << "pre" << arr[j] << " " << arr[j + 1] << std::endl;
               if (arr[j] > arr[j + 1])
               {
                   std::swap(arr[j], arr[j + 1]);
                   flag = true;
               }
               std::cout << "end:" << arr[j] << " " << arr[j + 1] << std::endl;
           }
           std::cout << "" << std::endl;
       }
   }
   
   void BubbleSort_2(std::vector<int> &arr)
   {
       bool flag = true;
       for (int i = 1; i < arr.size() && flag; i++)
       {
           flag = false;
           for (int j = 1; j < arr.size() - i + 1; j++)
           {
               std::cout << "pre" << arr[j] << " " << arr[j - 1] << std::endl;
               if (arr[j] < arr[j - 1])
               {
                   std::swap(arr[j], arr[j - 1]);
                   flag = true;
               }
               std::cout << "end:" << arr[j] << " " << arr[j - 1] << std::endl;
           }
           std::cout << "" << std::endl;
       }
   }
   
   //模板
   template <class T>
   void BubbleSortT(T data[], int n)
   {
       bool flag = true;
       for (int i = 0; i < n - 1 && flag; i++)
       {
           flag = false;
           for (int j = n - 1; j > i; j--)
           {
               std::cout << "pre:" << data[j] << " " << data[j - 1] << std::endl;
               if (data[j] < data[j - 1])
               {
                   std::swap(data[j], data[j - 1]);
                   flag = true;
               }
               std::cout << "end:" << data[j] << " " << data[j - 1] << std::endl;
           }
           std::cout << std::endl;
       }
   }
   

2. python

   def bubbleSort(arr):
   	for i in range(1, len(arr)):
           for j in range(0, len(arr)-i):
               if arr[j] > arr[j+1]:
                   swap(arr[i], arr[j])
       return arr
   

3. java

   public class BubbleSort implements IArraySort{
       
       @Override
       public int[] sort(int[] sourceArray) throws Exception {
           int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
           
           for (int i = 1; i < arr.length; i++) {
               boolean flag = true;
               for (int j = 0; j < arr.length - i; j++) {
                   if (arr[j] >arr[j + 1]) {
                       int temp = arr[j];
                       arr[j] = arr[i];
                       arr[i] = arr[j];
                       flag = false;
                   }
               }
               if (flag) {
                   break;
               }
           }
       }
       return arr;
       
   }
   

五、算法复杂度分析

当最好的情况，也就是要排序的表本身就是有序的，那么我们比较次数，根据最后改进的代码，可以推断出就是n-1次的比较，没有数

据交换，时间复杂度为 O( n)。当最坏的情况，即待排序表是逆序的情况， 此时需要

∑

i

=

2

N

i

−

1

\sum_{i=2}^N i-1

∑i=2N​i−1=1+2+3+… +(n-1) =

n

(

n

−

1

)

2

\frac{n(n-1)}{2}

2n(n−1)​次，并作等数量级的记录移动。因此，总的时间复杂度为 O(

n

2

n^2

n2)

六、 缺点

费时

六、参考资料

1. 一组动画演示冒泡排序
2. LeetCode 101：和你一起你轻松刷题（C++）
3. 大话数据结构
4. C++数据结构与算法 第四版
5. B站浙大数据结构