时间复杂度是O($n^2$)的排序算法有冒泡排序、选择排序、插入排序三种。
冒泡排序
两两比较，将大的往后移动即冒泡。
优化方案是如果不再比较，则剩余属于排序完成，则直接跳出循环；进一步的优化方案是每次比较只比较到上次比较的尾部。
选择排序
直接一个一个找最小的放至数组最前面。
优化方案是，每次找最小的和最大的，最小的放至最前面，最大的放至最后面，即二元排序。
插入排序
每次找最合适的位置，然后插入。实现方案包括交换法和移动法。交换即每次将要插入的与每个下标比较，如果小则交换；移动法不交换，将不符合的一个一个后移，直到找到合适的位置后放入。
其中冒泡排序和插入排序是稳定的排序算法，选择排序是不稳定的排序算法。时间复杂度都是O($n^2$)，空间复杂度都是O(1)。