冒泡排序 Bubble Sort

• 思想说明

  1. 冒泡排序中包含两种操作，一种是元素的比较，一种是元素的移动
  2. 冒泡排序只会操作相邻的两个数据，每次冒泡排序操作都会对相邻的两个元素进行比较，若不满足大小关系要求，则互换
  3. 一次冒泡至少会让一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作

• 分析

  1. 空间复杂度 O（1），是原地排序算法
  2. 最好时间复杂度 O（n），最坏时间复杂度 O（n^2），平均时间复杂度 O（n^2）
  3. 是稳定的排序算法

插入排序 Insertion Sort

• 思想说明

  1. 插入排序包含两种操作，一种是元素的比较，一种是元素的移动
  2. 将数组中的数据分为两个区间，已排序区和未排序区，动态地往有序集合中添加数据
  3. 取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序

• 分析

  1. 空间复杂度 O（1），是原地排序算法
  2. 最好时间复杂度 O（n），最坏时间复杂度 O（n^2），平均时间复杂度 O（n^2）
  3. 是稳定的排序算法

选择排序 Selection Sort

• 思想说明
  1. 选择排序包含两种操作，一种是元素的比较，一种是元素的移动
  2. 将数组中的数据，分为已排序区间和未排序区间
  3. 每次从未排序区间中找到最小的元素，放在已排序区间的末尾
• 分析
  1. 空间复杂度 O（1），是原地排序算法
  2. 最好时间复杂度 O（n^2），最坏时间复杂度 O（n^2），平均时间复杂度 O（n^2）
  3. 不是稳定的排序算法