Hark的数据结构与算法练习之冒泡排序
浏览数：17 /
时间：2015年06月08日
算法说明：
冒泡排序实际上是使用的最多的排序，逻辑是循环然后对相邻的数字进行比较，并交换数据。
例如有一个数组int[] arrayData = { 2, 3, 1, 5, 6, 7, 4, 65, 42 }，一共9个元素。
假设我们要做降序排序，那么首先全部9个元素从第1个元素开始进行两两比较，把小的元素放到后边；元素1小于元素2，那么元素1与元素2进行交换，然后元素2与元素3进行比较，元素2大于元素3，那么不进行交换，再进行元素3与元素4的比较…………以此类推最后比较到元素9。 这时元素9已经存在的是最小的数字啦。 接着我们继续比较前8个元素，再把最小的数字移动到元素8中。 然后前7个元素两两比较，前6个，前5个……以此类推，最后得出结果。
算法复杂度：
O(n2)
空间复杂度：
O(1)
代码：
使用语言：Java
/*
* 冒泡排序
*/
public class BubbleSort {
public static void main(String[] args) {
int[] arrayData = { 2, 3, 1, 5, 6, 7, 4, 65, 42 };
int temp = 0;
for (int i = 0; i < arrayData.length; i++) {
for (int j = 1; j < arrayData.length - i; j++) {
if (arrayData[j] > arrayData[j - 1]) {
temp = arrayData[j];
arrayData[j] = arrayData[j - 1];
arrayData[j - 1] = temp;
}
}
}
for (int integer : arrayData) {
System.out.print(integer);
System.out.print(" ");
}
}
}
结果是：
65 42 7 6 5 4 3 2 1
论证算法复杂度：因为是双层循环，所以最坏算法复杂度是O(n2)。
论证空间复杂度：因为作为临时空间进行数据交换只有一个temp变量，所以空间复杂度是O(1)
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
