day-9-排序（上）

一、如何分析一个“排序算法”

1.1 排序算法的执行效率

对于排序算法执行效率的分析，一般从以下几个方面来衡量：

• 最好情况、最坏情况、平均情况时间复杂度
• 时间复杂度的系数、常数、低阶
• 比较次数和交换（或移动）次数

1.2 排序算法的内存消耗

原地排序算法：特指空间复杂度是 O(1) 的排序算法。

1.3 排序算法的稳定性

二、冒泡排序

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。

三、插入排序

插入排序也包含两种操作，一种是元素的比较，一种是元素的移动。

四、选择排序

选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。

五、小结

要想分析、评价一个排序算法，需要从执行效率、内存消耗和稳定性三个方面来看。

这三种时间复杂度为 O(n2) 的排序算法中，冒泡排序、选择排序，可能就纯粹停留在理论的层面了，学习的目的也只是为了开拓思维，实际开发中应用并不多，但是插入排序还是挺有用的。