从深水区开始冒泡

本文主要是介绍从深水区开始冒泡，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一. 冒泡算法基本思想

冒泡排序也称为交换排序算法，从一组无序的队列，通过相邻的两个元素进行两两比较，根据大小交换位置，筛选最大或者最小的元素到有序队列的尾部，周而复始，直到整个队列的元素从无序变成有序。

二. 冒泡算法核心逻辑

1. 以升序为例子，筛选最大的元素到队列尾部，默认队列为 [ 4，3，5，2 ]

2. 以4作为最大元素开始，跟3作比较，4比3大，4与3交换，交换后的队列为[ 3，4，5，2 ]

3. 4继续跟5作比较，4比5小，不交换位置，最大元素变为5

4. 以5作为最大元素，继续跟2做比较，5比2大，交换位置，5作为最大值已到达队列尾部，成为有序队列的一部分，队列为 [ 3，4，2，5 ]

5. 3开始作为最大元素，跟相邻4作比较，3比4小，不交换位置，最大元素变为4

6. 以4作为最大元素，继续跟相邻元素2作比较，4比2大，交换位置，交换后队列为[ 3，2，4，5 ]

7. 4继续跟相邻元素5作比较，由于5是有序队列的一部分，因此4成为了有序队列的一部分，队列为[ 3，2，4，5 ]

8. 3开始作为最大元素，跟相邻的2作比较，3比2大，交换位置，交换后队列为[ 2，3，4，5 ]

9. 3继续跟相邻元素4作比较，由于4是有序队列的一部分，因此3成为了有序队列的一部分，队列为[ 2，3，4，5 ]

10. 2开始作为最大元素，跟相邻3作比较，由于3是有序队列的一部分，因此2成为有序队列的一部分，队列为[ 2，3，4，5 ]

11. 最终整个无序的队列变成了有序的队列 [ 2，3，4，5 ]

三. 冒泡算法图示

四. 冒泡算法代码

1. 基础冒泡排序

        public static void BubbleSort(){int[] arrays = new[] { 4, 3, 5, 2 };//元素队列for (int i = 0; i < arrays.Length; i++) //外层循环把队列的每一元素参与运算{for (int j = 0; j < arrays.Length - 1; j++)  //内层循环把队列最大值移动到队列尾部，成为有序队列的一部分{if (arrays[j] > arrays[j + 1]) //作比较，交换元素{int temp = arrays[j + 1];//临时变量arrays[j + 1] = arrays[j];//交换元素arrays[j] = temp; }}}}

2. 优化冒泡排序，添加标志向量

        public static void OptimizeBubbleSortInLabel(){int[] arrays = new[] { 4, 3, 5, 2 };bool change = false; //添加标志变量for (int i = 0; i < arrays.Length; i++){for (int j = 0; j < arrays.Length - 1; j++){if (arrays[j] > arrays[j + 1]){int temp = arrays[j + 1];arrays[j + 1] = arrays[j];arrays[j] = temp;change = true;//发生交换，说明队列存在无序情况}}if (!change) break;//没有发生交换就中断，队列已经有序}}

3. 优化冒泡排序，减少交换次数

        /// <summary>/// 优化冒泡排序执行次数，忽略有序队列，对无序队列进行排序，内层循环减去已经排序好的数量。/// </summary>/// <param name="arrays"></param>public static void OptimizeBubbleSortInCount(){int[] arrays = new[] { 4, 3, 5, 2 };//元素队列bool change = false;for (int i = 0; i < arrays.Length; i++){for (int j = 0; j < arrays.Length -1-i; j++) //减去有序队列，只对无序队列进行交换{if (arrays[j] > arrays[j + 1]){int temp = arrays[j + 1];arrays[j + 1] = arrays[j];arrays[j] = temp;change = true;}}if (!change) break;}}

五. 冒泡算法性能分析（以第四部分第3代码为例子）

1. 冒泡排序时间复杂度

在正序的特殊情况下，例如[1,2,3,4,5],经过n-1次的比较，没有元素交换，也就是冒泡排序在最好的情况下的时间复杂度是O(n)
在逆序的特殊情况下，例如[5,4,3,2,1],经过n(n-1)/2次的比较，期间发生了3n(n-1)/2次的交换，这是冒泡排序在最坏情况下的时间复杂度O(n^2)
在杂乱无序的正常情况下，例如[4,3,5,1,2],冒泡排序的平均时间复杂度为O(n^2)