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

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

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

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

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

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

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

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

舞台

photo by Rob Laughter

空空的舞台
在等待
一束光的开启

时空的那头
人影晃动
激扬的头发
弹奏着光的琴弦

天生的歌者
闪耀于舞台中央
将每一串音符
唱出生命的色彩

真正的歌者
纵然没有舞台
也要把歌声
唱与高山,唱与大海

但此刻
空空的舞台
还在等待
一束光的开启

那些路边的蟋蟀
趁夜色尚未到来
开始寻找,今夜
吟唱的舞台

photo by Yvette de Wit