时间复杂度为 O(n^2) 的排序算法
💡
原文中文，约2800字，阅读约需7分钟。
📝
内容提要
对于小规模数据，O(n²) 排序算法可能更高效。插入排序适合部分有序数组，希尔排序通过交换不相邻元素提高效率。选择排序每次选最小值放到已排序区末尾，冒泡排序通过比较和交换相邻元素排序。插入排序和冒泡排序是稳定的，选择排序不稳定。希尔排序适合大规模数组，插入排序在小数据量时表现优异。
🎯
关键要点
- 对于小规模数据，O(n²) 排序算法可能更高效。
- 时间复杂度并不代表实际代码的执行时间，O(n²) 算法在小规模数据时可能比 O(nlogn) 更快。
- 稳定性：排序后等值元素相对位置不变为稳定排序，反之为不稳定排序。
- 插入排序适合部分有序数组，效率高。
- 插入排序的空间复杂度为 O(1)，是原地排序且稳定。
- 希尔排序通过交换不相邻元素提高效率，适合大规模数组。
- 选择排序每次选择未排序数组中的最小值放到已排序区末尾，空间复杂度为 O(1)，是原地排序但不稳定。
- 冒泡排序通过比较和交换相邻元素实现排序，空间复杂度为 O(1)，是原地排序且稳定。
❓
延伸问答
O(n²) 排序算法适合什么样的数据规模？
O(n²) 排序算法适合小规模数据，可能比 O(nlogn) 更高效。
插入排序的空间复杂度是多少？
插入排序的空间复杂度为 O(1)，是原地排序且稳定。
希尔排序是如何提高排序效率的？
希尔排序通过交换不相邻的元素对数组的局部进行排序，从而提高效率。
选择排序的稳定性如何？
选择排序是不稳定的，会改变等值元素之间的相对位置。
冒泡排序的最佳时间复杂度是多少？
经过优化后的冒泡排序最佳时间复杂度为 O(n)。
在什么情况下插入排序表现优异？
插入排序在部分有序数组或数据量较小的情况下表现优异。
➡️
