排序算法---冒泡排序

话说这冒泡排序好久都没有用过了，忘得差不多了，但是由于目前的需要，只能再次重新学习了一下。

各种算法最好是用C/C++，因为执行效率高啊，在JAVA平台运行这些算法有些不适合，不过这个冒泡排序姑且用JAVA来测试一下。

下图是对它的各种复杂度的评价

最差时间复杂度 最优时间复杂度 平均时间复杂度 最差空间复杂度 最佳算法

O(n²)

O(n)

O(n²)

O(n) total, O(1)auxiliary

No

性能分析：

若记录序列的初始状态为"正序"，则冒泡排序过程只需进行一趟排序，在排序过程中只需进行n-1次交换，且不移动记录；反之，若记录序列的初始状态为"逆序"，则需进行n(n-1)/2次比较和记录移动。因此冒泡排序总的时间复杂度为O(n*n)。

 

下面是冒泡排序的执行过程：

冒泡排序算法的运作如下：

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

下面通过一个例子来查看这个算法每一轮知道最后的执行结果：

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个数字中再次执行上述的过程，知道最后

评论

1 楼 thrillerzw 2013-06-03  

外层循环改为do while可以提高到最优时间复杂度O(n)