2020-08-02Learning notes / Algorithm / Sort7 minutes read (About 1080 words)

冒泡排序

1.基本思想

冒泡排序是一种交换排序，核心是冒泡，把数组中最小的那个往上冒，冒的过程就是和他相邻的元素交换。
重复走访要排序的数列，通过两两比较相邻记录的排序码。排序过程中每次从后往前冒一个最小值，且每次能确定一个数在序列中的最终位置。若发生逆序，则交换；有俩种方式进行冒泡，一种是先把小的冒泡到前边去，另一种是把大的元素冒泡到后边。

2.图解

3.实现逻辑

● 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
● 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。,每次遍历都会当前遍历最大的数放在最后，最后的元素应该会是最大的数。
● 所以上次遍历后产生的最大的数已经在后面了，所以不用再对其进行遍历了，所以每次两两交换的数量会变小（即减i）
● 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

通过两层循环控制：
● 第一个循环（外循环），负责把需要冒泡的那个数字排除在外；
● 第二个循环（内循环），负责两两比较交换。

4.举个栗子

假如有数组为[10,1,35,61,89,36,55]

第一趟排序：
第一次排序：10和1比较，10大于1，交换位置 [1,10,35,61,89,36,55]
第二次排序：10和35比较，10小于35，不交换位置 [1,10,35,61,89,36,55]
第三次排序：35和61比较，35小于61，不交换位置 [1,10,35,61,89,36,55]
第四次排序：61和89比较，61小于89，不交换位置 [1,10,35,61,89,36,55]
第五次排序：89和36比较，89大于36，交换位置 [1,10,35,61,36,89,55]
第六次排序：89和55比较，89大于55，交换位置 [1,10,35,61,36,55,89]
第一趟总共进行了六次比较，排序结果： [1,10,35,61,36,55,89]

第二趟排序：
第一次排序：1和10比较，1小于10，不交换位置 [1,10,35,61,36,55,89]
第二次排序：10和35比较，10小于35，不交换位置 [1,10,35,61,36,55,89]
第三次排序：35和61比较，35小于61，不交换位置 [1,10,35,61,36,55,89]
第四次排序：61和36比较，61大于36，交换位置 [1,10,35,36,61,55,89]
第五次排序：61和55比较，61大于55，交换位置 [1,10,35,36,55,61,89]
第二趟总共进行了五次比较，排序结果： [1,10,35,36,55,61,89]

按这样子的思路以此类推下去
假如数组有n个元素

第一个for循环
从上面的分析可以看到，第一趟遍历走了n次，把n个元素里最大的元素移到本次遍历的最后端
第二次遍历走了n-1次，把n-1个元素里最大的元素移到本次遍历的最后一端，
因为倒数第二次遍历，就可以把2元素里最大的移到本次遍历的最后一端，那么，就不用再遍历最后一个元素了，所以代码中第一个for循环只需要n-1；

第二个for循环
从上面的分析可以看到，第一趟遍历走了n次，把n个元素里最大的元素移到本次遍历的最后端
第二次遍历走了n-1次，把n-1个元素里最大的元素移到本次遍历的最后一端，
同样的，是不是每次遍历，都会少遍历一个元素呢，所以第二个for循环只需要n-i-1

5.代码实现及详解

c++版本

void bubble_sort(int arr[], int len)  
{  
    int i, j;  
    for (i = 0; i < len-1; i++)    //总遍历的次数
        for (j = 0; j < len - 1 -i; j++)  //每次遍历需要走的个数
            if (arr[j] > arr[j+1])
                swap(arr[j], arr[j+1]);  
}

6.分析

如果有n个数，最多需要走n-1次遍历就可以排好
平均时间复杂度：O(n^2)
最佳时间复杂度：O(n)
最差时间复杂度：O(n^2)
空间复杂度：O(1)

7.参考

https://zhuanlan.zhihu.com/p/122284534
https://www.cnblogs.com/bigdata-stone/p/10464243.html

#Algorithm