《算法》读书笔记：八大排序算法解析

"读书笔记1——算法学习记录" 这篇读书笔记主要涵盖了《算法》一书中的部分内容，特别是经典八大排序算法的介绍。笔记作者是软工181班的林鑫，于2020年4月15日至6月2日阅读并整理了相关知识。 1. 冒泡排序 (Bubble Sort) 冒泡排序是一种基础的排序算法，通过不断比较相邻元素并交换来实现排序。其主要步骤包括： - 比较相邻的元素，如果前一个元素大于后一个元素，则交换它们的位置。 - 对每一对相邻元素重复此过程，从开始的第一对到最后的一对。 - 重复以上步骤，直到整个序列无需再交换，即排序完成。 1.2 算法描述 冒泡排序的基本思想是多次遍历数列，每次遍历都将最大（或最小）的元素“冒泡”到序列的末端。 1.3 代码实现 虽然代码没有给出，但冒泡排序的典型实现通常包含两个嵌套循环，外层循环控制遍历次数，内层循环用于比较和交换。 1.4 算法分析 - 最佳情况：当输入序列已经是有序的，冒泡排序只需进行一次遍历，时间复杂度为O(n)。 - 最差情况：当输入序列是逆序时，需要进行n*(n-1)/2次比较，时间复杂度为O(n^2)。 - 平均情况：同样为O(n^2)，因为即使在部分有序的情况下，冒泡排序的时间复杂度也不会低于O(n^2)。 2. 选择排序 (Selection Sort) 选择排序是一种稳定的排序算法，特点是不论何种数据进去都是O(n^2)的时间复杂度，适用于数据量较小的情况。 2.1 算法描述 选择排序的基本思路是： - 首先在未排序的序列中找到最小（或最大）元素，存放到排序序列的起始位置。 - 然后，再从剩余未排序元素中继续寻找最小（或最大）元素，放到已排序序列的末尾。 - 重复此过程，直到所有元素均排序完毕。 2.2 算法分析 - 选择排序在任何情况下都需要进行n(n-1)/2次比较，因此时间复杂度总是O(n^2)。 - 虽然效率不高，但它不占用额外的内存空间，属于原地排序。 笔记还提到了其他经典排序算法如插入排序、快速排序、归并排序等，以及二叉查找树、图论相关的知识，如背包问题、队列和栈的应用、无向图和有向图的处理，还有最小生成树和最短路径算法等，但这些内容在提供的摘要中并未展开详细讨论。 总结，这篇读书笔记主要聚焦在冒泡排序和选择排序这两种简单排序算法上，介绍了它们的原理、描述、实现和性能分析，为后续学习更复杂的算法打下了基础。