软考-软件设计师：排序算法-交换类排序：冒泡排序、快速排序 作者：马育民 • 2025-04-15 08:49 • 阅读：10001 # 冒泡排序(经常考) 通过 **相邻元素之间的比较和交换**，按照前小后大或者前大后小规则交换。 >由于整个排序的过程元素就像水底下的气泡一样逐渐向上冒，因此称为冒泡算法。 1. 第1趟：第1个元素与第2个元素比较，大则交换 第2与第3个比较，大则交换，依次类推 如此操作，最后一个元素就是最大值 2. 第2趟：以此类推，完成排序 3. 第n趟，完成排序 ### 例子 将 `T=(25,56,49,78,11,65,41,36)` 按照前大后小型的排序 冒泡排序执行步骤： ``` 第1趟：25,49,56,11,65,41,36,【78】 第2趟：25,49,11,56,41,36,【65,78】 第3趟：25,11,49,41,36,【56,65,78】 第4趟：11,25,41,36,【49,56,65,78】 第5趟：11,25,36【41,49,56,65,78】, ``` ### 时间复杂度 ``` O(n²) ``` **解释：**n个元素，每次比较 `n` 个元素（实际上不到n），共比较 `n-1` 次（最后一次必须要比较），所以总共需要 `n (n-1)`，渐进法表示：`O(n²)` ### 空间复杂度 O(1) ### 算法稳定性 稳定 # 快速排序 快速排序采用的是 **分治法**：将原问题分解成 **若干个** 规模更小但结构与原问题相似的 **子问题**。通过 **递归** 解决这些 **子问题**，然后再将这些 **子问题的 解** 组合成 **原问题的 解**。 ### 步骤 1. 从待排序序列中任取一个元素（例如第一个）作为它的中心，比其小（或者相等）的元素放前，比其大的元素放后面。此时得到两组元素 2. 对两组元素选择中心元素，并比较、调整顺序 3. 以此类推，直到每组元素只剩一个。此时就是有序序列了 ### 例子 将 `T=(49,38,65,97,76,13,27,50)` 排序 快速排序步骤： **第一趟：** 选择第一个数作为中心 `49`，与各个元素比较，小的放前，大的放后，结果：`【27,38,13】49【76,97,65,50】` **第二趟：** 选择 **每组** **第一个数作为中心**，即： - 第一组是 `27` - 第二组是 `76` 分别与两组元素比较，小的放前，大的放后，结果：`【13,】27,【38】,49,【50,65】76,【97】` **第三趟：** 同上，最终结果：`13,27,38,49,65,76,97` ### 中心元素（基准元素） 一般选第一个，也可以是中位数，或 最后一个 ### 时间复杂度 O(nlog₂n) ### 最差的情况 原本就基本有序，此时选取 **第一个元素**作为中心点，没有分成两组，一直是一组 **解决：**选取处于 **中位数** 的元素作为中心点 ### 空间复杂度 辅助空间 - 空间复杂度默认为 `O(1)` - 需要辅助空间存储左侧数组和右侧数组时，空间复杂度为`O(n)` - 需要记录所有基准元素时，空间复杂度为 `O(log₂n)` ### 算法稳定性 不稳定，任意选取中心点，然后与各个元素比较 # 题 对数组 `A=(2,8,7,1,3,5,6,4)` 用快速排序算法的划分方法进行一趟划分后得到的数组A为（ ）(非递减排序，以最后一个元素为基准元素）。进行一趟划分的计算时间为( ) A、(1,2,8,7,3,5,6,4) B、(1,2,3,4,8,7,5,6) C、(2,3,1,4,7,5,6,8) D、(2,1,3,4,8,7,5,6) A、O(1) B、O(lgn) C、O(n) D、O(nlgn) ### 第1问-分析 - `非递减排序`，也就是递增排序，执行第一趟后，**最后一个元素是最大值**，所以最后一个元素是 `8`，所以排除 ABD - `最后一个元素为基准元素`：所以 `4` 是基准元素，第一个元素 `2` 比 `4` 小，不动，所以第一趟执行后，第一个元素还是 `2` ### 第2问-分析 基准元素要与其他 `n-1` 个元素比较，所以执行 `n-1` 次，渐进法表示时间复杂度：`O(n)` ### 第1问-答案 C ### 第2问-答案 C # 题 对n个数排序，最坏情况下时间复杂度最低的算法是（）排序算法。 A、插入 B、冒泡 C、归并 D、快速 ### 分析 插入排序，最坏的情况，时间复杂度是 `O(n²)` 冒泡排序，最坏的情况，时间复杂度是 `O(n²)` 归并排序，最坏的情况，时间复杂度是 `O(nlog₂n)` 快速排序，最坏的情况，时间复杂度是 `O(n²)` 复杂度 **最低** 的算法，也就是 **效率最高** 原文出处：http://malaoshi.top/show_1GWwqG5vju8.html