锁定老帖子 主题:排序算法---冒泡排序
精华帖 (0) :: 良好帖 (0) :: 新手帖 (1) :: 隐藏帖 (1)
|
||||||
---|---|---|---|---|---|---|
作者 | 正文 | |||||
发表时间:2011-09-27
话说这冒泡排序好久都没有用过了,忘得差不多了,但是由于目前的需要,只能再次重新学习了一下。 各种算法最好是用C/C++,因为执行效率高啊,在JAVA平台运行这些算法有些不适合,不过这个冒泡排序姑且用JAVA来测试一下。 下图是对它的各种复杂度的评价
性能分析: 若记录序列的初始状态为"正序",则冒泡排序过程只需进行一趟排序,在排序过程中只需进行n-1次交换,且不移动记录;反之,若记录序列的初始状态为"逆序",则需进行n(n-1)/2次比较和记录移动。因此冒泡排序总的时间复杂度为O(n*n)。
下面是冒泡排序的执行过程:
冒泡排序算法的运作如下: 下面通过一个例子来查看这个算法每一轮知道最后的执行结果:
package test02; import java.util.Arrays; public class Test01 { public static void main(String args[]) { int[] a = {3,5,2,4,6}; sort(a, a.length); System.out.println("最终结果========================="); System.out.println(Arrays.toString(a)); } public static void sort(int[] array,int size) { int i,j,temp; for(i=0;i<size;i++) { for(j=0;j<size-i-1;j++) { if(array[j]>array[j+1]) { temp = array[j]; array[j] = array[j+1]; array[j+1] = temp; } System.out.println(Arrays.toString(array)); } System.out.println("第"+i+"次----------------------"); } } } 运行结果如下:
[3, 5, 2, 4, 6] [3, 2, 5, 4, 6] [3, 2, 4, 5, 6] [3, 2, 4, 5, 6] 第0次---------------------- [2, 3, 4, 5, 6] [2, 3, 4, 5, 6] [2, 3, 4, 5, 6] 第1次---------------------- [2, 3, 4, 5, 6] [2, 3, 4, 5, 6] 第2次---------------------- [2, 3, 4, 5, 6] 第3次---------------------- 第4次---------------------- 最终结果========================= [2, 3, 4, 5, 6] 对结果的分析: 第一轮:首先3和5比较,3不大于5,所以第一次比较不动,然后5和2比较,5大于2,所以交换5和2,变成 3,2,5,4,6,然后5和4比较,5>4,交换5和4,变成:3,2,4,5,6,5再和6比较,5小于6,所以不变。这就是第一轮的执行过程,也就是每一次都会沉下一个最大的数字 第二轮:由于沉下了最大的数字6,所以剩下了2,3,4,5。在这4个数字中再次执行上述的过程,知道最后 声明:ITeye文章版权属于作者,受法律保护。没有作者书面许可不得转载。
推荐链接
|
||||||
返回顶楼 | ||||||
发表时间:2011-09-28
学过数据结构的人,都知道。
|
||||||
返回顶楼 | ||||||
浏览 2606 次