软件测试修炼之路 A Tester

冒泡排序

2016-05-25
Dex

算法概念

冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。

它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。

这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端,故名。

以上来自百度百科。

冒泡排序最好的时间复杂度为O(n)。

冒泡排序的最坏时间复杂度为O(n^2)。

冒泡排序总的平均时间复杂度为O(n^2)。

算法代码(Java)

//冒泡排序算法
public class BubbleSort {
	public void BubbleSort(int[] data) {
		for(int i = data.length - 1; i > 0; --i){
			for(int j = 0; j < i; j++){
				if(data[j+1] < data[j]){
					int temp = data[j];
					data[j] = data[j+1];
					data[j+1] = temp;
				}
			}
		}
	}

	public static void main(String[] args) {
		
		int[] x = {6, 2, 4, 1, 5, 9};
		BubbleSort sort = new BubbleSort();
		sort.BubbleSort(x);
		//输出排序后的数组
		for(int i = 0; i < x.length; i++){
			System.out.print(x[i]);
		}
		
	}

}

算法单步执行过程

数列:[6, 2, 4, 1, 5, 9]

共进行5趟外循环。

第一趟外循环:

i = 5, j = 0: [2, 6, 4, 1, 5, 9]
i = 5, j = 1: [2, 4, 6, 1, 5, 9]
i = 5, j = 2: [2, 4, 1, 6, 5, 9]
i = 5, j = 3: [2, 4, 1, 5, 6, 9]
i = 5, j = 4: 无变化

得到:[2, 4, 1, 5, 6, 9]
第一轮外循环冒泡排序得到的是9,是数列中的最大数。

第二趟外循环:

i = 4, j = 0: 无变化
i = 4, j = 1: [2, 1, 4, 5, 6, 9]
i = 4, j = 2: 无变化
i = 4, j = 3: 无变化

得到: [2, 1, 4, 5, 6, 9]
第二轮外循环冒泡排序得到的是6。

第三趟外循环:

i = 3, j = 0: [1, 2, 4, 5, 6, 9]
i = 3, j = 1: 无变化
i = 3, j = 2: 无变化

得到: [1, 2, 4, 5, 6, 9]
第三轮外循环冒泡排序得到的数是5。

第四趟外循环:

i = 2, j = 0: 无变化
i = 2, j = 1: 无变化

得到: [1, 2, 4, 5, 6, 9]
第四轮外循环冒泡排序得到的数是4。

第五趟外循环:

i = 1, j = 0: 无变化

得到: [1, 2, 4, 5, 6, 9]
第五轮外循环冒泡排序得到的数是1, 2。

虽然在第三趟外循环时已经拿到最终的排序结果,但是程序依然会进行下去,只不过只是进行了对比,未进行移动数据。


Similar Posts

上一篇 Android开发

下一篇 快速排序

Comments