博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
【算法-排序之一】冒泡排序
阅读量:5823 次
发布时间:2019-06-18

本文共 778 字,大约阅读时间需要 2 分钟。

hot3.png

算法-排序之冒泡排序

如果数据按照一定的顺序进行排序,数据处理的效率将显著的提高。算法是编程的精髓,一个高效而合适的算法能极大的减少时间消耗与空间消耗,提到“合适”是因为没有哪个算法可以在所有情况下都表现出色,同样是排序,在不同数据规模下各种排序算法有不同的效能表现,选择合适的解决算法的才能最大限度地提高效率。

1.冒泡算法BubbleSort是常用排序算法之一,它的核心是让大(或小)的数据像水泡一样冒到最上端,这是通过不断地比较两个相邻数据的大小,前者大于后者则交换位置来实现冒泡。

如下示例:

 public static int[] BubbleSort(int num[]){  for(int i=0;i
num[j]){     int temp = num[j];     num[j] = num[j-1];     num[j-1] = temp;    }   }  }  return num; }

图解如下:

排序一遍后变成

依次类推,效果犹如把最大数“冒”上去。

需要注意的细节是,对于n个数据,只需要排n-1次,故控制排序遍数的i起始值为1而不是0.在每次排序中,上次排好的数不需要再进行比较,故控制每次排序结束位置变了j的上限是num-i,随着排序次数i增加,需要排序的位置越靠前。

2. 时间复杂度

冒泡排序的主要时间消耗是比较,第一趟序比较n-1次,随后依次递减n-2....1,则总比较(n-1)+(n-2)+...+3+2+1=(n*2-n)/2,故其时间复杂度为O(n*2).

3.空间复杂度

整个排序过程需要一个temp的空间用于交换数据,故为空间复杂度为O(1).

转载于:https://my.oschina.net/Chaos777/blog/210664

你可能感兴趣的文章
贪吃蛇
查看>>
EventSystem
查看>>
用WINSOCK API实现同步非阻塞方式的网络通讯
查看>>
玩一玩博客,嘿嘿
查看>>
P1352 没有上司的舞会
查看>>
ios11文件夹
查看>>
【HLOJ 559】好朋友的题
查看>>
Electric Fence(皮克定理)
查看>>
nvl 在mysql中如何处理
查看>>
MyEclipse 快捷键
查看>>
快速傅里叶变换FFT
查看>>
大数据常用基本算法
查看>>
JavaScript学习笔记(十三)——生成器(generator)
查看>>
hibernate保存失败
查看>>
MySQL增量订阅&消费组件Canal POC
查看>>
Sqlite多线程
查看>>
数据结构-时间复杂度
查看>>
对象与字符串相互转换
查看>>
[NOIp2017提高组]小凯的疑惑
查看>>
《C程序设计语言》练习1-5
查看>>