Java 基础篇-冒泡排序

在开发中,对一组数据进行有序地排列是经常需要做的事情,所以掌握几种甚至更多的排序算法是绝对有必要的:
问题:设有一数组,其大小为10个元素(int   arr[10])数组内的数据是无序。现在要求我们通过编程将这个无序的数组变成一个从小到大排序的数组(从下标为0开始)
冒泡排序冒泡排序是比较相邻两数的大小来完成排序的。以升序排序为例,每趟排序完成之后,比较边界中的最大值就沉入底部,比较边界就向前移动一个位置。所以,第二趟排序开始时,比较边界是[0,n-2]。对于长度为n的序列,最多需要n趟完成排序,所以冒泡排序就由两层循环构成,最外层循环用于控制排序的趟数,最内层循环用于比较相邻数字的大小并在本趟排序完成时更新比较边界。

具体代码如下:

// 冒泡排序
	public static void bubbleSort(int[] arr) {
		int temp = 0, len = arr.length;
		int compareRange = len - 1;// 冒泡排序中,参与比较的数字的边界。
		// 冒泡排序主要是比较相邻两个数字的大小,以升序排列为例,如果前侧数字大于后侧数字,就进行交换,一直到比较边界。
		for (int i = 0; i < len; i++) {// n个数使用冒泡排序,最多需要n趟完成排序。最外层循环用于控制排序趟数
			for (int j = 1; j <= compareRange; j++) {
				if (arr[j - 1] > arr[j]) {
					temp = arr[j - 1];
					arr[j - 1] = arr[j];
					arr[j] = temp;
				}
			}
			compareRange--;// 每进行一趟排序,序列中最大数字就沉到底部,比较边界就向前移动一个位置。
		}
		System.out.println("排序后数组" + Arrays.toString(arr));
	}

在排序后期可能数组已经有序了而算法却还在一趟趟的比较数组元素大小,可以引入一个标记,如果在一趟排序中,数组元素没有发生过交换说明数组已经有序,跳出循环即可。优化后的代码如下:

public static void bubbleSort2(int[] arr) {
		int temp = 0, len = arr.length;
		int compareRange = len - 1;// 冒泡排序中,参与比较的数字的边界。
		boolean flag = true;// 标记排序时候已经提前完成
		int compareCounter = 0;
		// 冒泡排序主要是比较相邻两个数字的大小,以升序排列为例,如果前侧数字大于后侧数字,就进行交换,一直到比较边界。
		while (flag) {
			flag = false;
			for (int j = 1; j <= compareRange; j++) {
				if (arr[j - 1] > arr[j]) {
					temp = arr[j - 1];
					arr[j - 1] = arr[j];
					arr[j] = temp;
					flag = true;
				}
			}
			compareCounter++;
			compareRange--;// 每进行一趟排序,序列中最大数字就沉到底部,比较边界就向前移动一个位置。
		}
		System.out.println("优化后排序次数:" + (compareCounter - 1));
		System.out.println("排序后数组" + Arrays.toString(arr));
	}

还可以利用这种标记的方法还可以检测数组是否有序,遍历一个数组比较其大小,对于满足要求的元素进行交换,如果不会发生交换则数组就是有序的,否则是无序的。  两种方法的排序结果如下所示:

本文由 学习web技术的分享 作者:debug 发表,其版权均为 学习web技术的分享 所有,文章内容系作者个人观点,不代表 学习web技术的分享 对观点赞同或支持。如需转载,请注明文章来源。
8

发表评论