排序算法通览

排序算法

排序，字面理解就是排列顺序。排序算法的主要职能是将给定的一串数据按照特定的顺序将其重新排列，其实就是数字的升序/降序排列。
因此，排序算法的主要操作分为两个步骤：比较、交换。

衡量指标

1. 时间复杂度

即分析一个排序算法的时间复杂度，分别给出最好情况、最坏情况、平均情况时间复杂度。

2. 空间复杂度

分析算法的内存消耗，对于原地排序的算法，其空间复杂度为。

3. 稳定性

如果排序的序列中存在值相等的元素，经过排序后，相等元素之间原有的顺序不变。
即元素在未被排序之前，其所处的位置是否发声改变。

排序算法性能速查表

名称	时间复杂度			空间复杂度	是否稳定性	是否原地排序
	平均	最好情况	最坏情况
冒泡排序					是	是
快排序					否	是
直接插入					是	是
选择排序					否	是
归并排序					是	否

常见问题

1. 插入排序与冒泡排序的比较

虽然二者的时间复杂度相同，但是平均情况下，冒泡排序算法中元素交换的次数为原始数据的逆序度，对比插入排序为，随着数据规模的增长，插入排序有性能优势，而冒泡排序的优化空间有限。

2. 平均情况下，插入排序比选择排序快

比较二者的数据比较次数及即可：

• 插入排序：
• 选择排序：

  参考

  排序算法通览
  可视化展示