排序——冒泡、插入、选择
1、排序算法
|排序算法|时间复杂度|是否基于比较|
|—|—|—|
|冒泡、插入、选择|O(n2)|是|
|快排、归并|O(nlogn)|是|
|桶、计数、基数|O(n)|否|
2、如何分析一个排序算法？
（1）排序算法的执行效率：最好情况、最坏情况、平均情况时间复杂度；间复杂度的系数、常数 、低阶；比较次数和交换（或移动）次数；
（2）排序算法的内存消耗
（3）排序算法的稳定性
3、冒泡排序（Bubble Sort）
冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。
冒泡过程还可以优化。当某次冒泡操作已经没有数据交换时，说明已经达到完全有序，不用再继续执行后续的冒泡操作。
4、插入排序（Insertion Sort）
将数组中的数据分为两个区间，已排序区间和未排序区间。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。
5、选择排序（Selection Sort）
选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。
