冒泡排序

具体实现

GitHub版本库的冒泡排序。

算法实现

  1. 根据需要排序的个数,进行倒序循环,起点为待排序个数,依次递减,直到1为止。
  2. 第二层循环,从第一个元素(索引为0)开始,到待排序个数实时减一。
  3. 第一次比较,找到比第一个数小的话,进行交换,那么最小的数,必定在第一的位置。
  4. 第二层循环,终止条件$j< $i-1的原因是每次第一层循环完后,会把较少的值交换,故下次不需要再进行排序。

耗时分析

机器配置 ThinkPad T440s CPU i5-4300U Memory 8GB
num 1000 sort cost time is 0.0314781665802 s
num 10000 sort cost time is 2.6688499450684 s
num 100000 sort cost time is 287.84617590904 s

算法分析

最坏时间复杂度 {\displaystyle O(n^{2})} O(n^{2})
最优时间复杂度 {\displaystyle O(n)} O(n)
平均时间复杂度 {\displaystyle O(n^{2})} O(n^{2})
空间复杂度 总共 {\displaystyle O(n)} O(n),需要辅助空间 {\displaystyle O(1)} O(1)

参考链接

  1. 冒泡排序

发表评论

电子邮件地址不会被公开。 必填项已用*标注