java算法的时间和空间复杂度_Java菜鸟教程 冒泡排序，时间复杂度和空间复杂度...
最近，笔者学习了冒泡排序，在此简单分享一下。
冒泡排序的原理：
对于一个数组，冒泡排序算法会比较相邻的两项的大小，并进行交换。
对每一对相邻的元素做同样的调整，如：第一个和第二个，第二个和第三个，第三个和第四个等等，以此类推。这样下来，最后的元素会是最大的。
重复以上步骤。如果有n个元素，则第一次循环进行n-1次，第二次循环进行n-2次，…………，第n-j次循环过后，会按大小顺序排出j个较大的数。
持续以上的步骤，直到没有任何一堆数字需要比较。
冒泡原理的简单应用：
任务：排序：4，9，10，5，7
时间复杂度与空间复杂度
时间复杂度：时间复杂度是一个函数，定量描述了算法的运算时间，用大O符号来表示。在计算的时候，先找出算法基本操作的执行次数，即为T(n)，然后找到它的同数量级，即为f(n)，如果T(n)与f(n)的比值求极限可得到一个常数c，那么时间复杂度T(n)=O(f(n))。
上面的冒泡排序的时间复杂度计算(计算下方的for循环)：T(n) = (4n+1)n，f(n) = n*n，c = 4，则时间复杂度为：T(n) = O(n*n)
空间复杂度：空间复杂度是运行完一个程序所需要的内存的大小。这里包括了存储算法本身所需要的空间，输入与输出数据所占空间，以及一些临时变量(比如上面的h)所占用的空间。一般而言，我们只比较额外空间，来比较算法的空间优越性。
上面的冒泡排序的临时变量所占空间不随处理数据n的大小改变而改变，则空间复杂度为O(1)。
优化冒泡排序：
如果给出的数据为1，2，3，4，5，6，7，9，8，要求进行排序，那么只需要进行一次交换即可。但此时程序仍然会继续检测到1为止。此时需要进行优化。
以上如果有表述不当之处，还请指出更正！
2017-8-20 上午
折叠