深入理解排序算法(一):插入排序、冒泡排序、选择排序

写在前面:开始系统地梳理知识,暂且先把一些想法记录下来,后续有时间再做进一步整理和完善,比如展开文字、配以实例和图片等。

排序算法是最常用的算法之一,分析排序算法的三个重要指标:时间复杂度、空间复杂度以及稳定性。

基于比较的排序算法时间复杂度一般在O(nlogn)到O(n2)之间。

空间复杂度为O(1)的排序称为就地(in-place)排序,或者原址排序,非就地排序的空间复杂度一般为O(n)。

稳定性指的是序列中相等的元素在排序后的前后位置是否会发生变化,如果不变则排序算法是稳定的(stable),否则为不稳定。

排序可以按从小到大,也可以按从大到小的顺序排列,后面我们在讨论和实现算法时都以前者为准。

插入排序、冒泡排序、选择排序是三种最简单直接的排序算法,都是基于比较+交换,由内外两层循环实现,其中外循环次数为n-1,内循环次数跟外循环的循环变量相关,平均时间复杂度为O(n2),空间复杂度为O(1)。 继续阅读“深入理解排序算法(一):插入排序、冒泡排序、选择排序”