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