冒泡排序

排序

排序也称排序算法(Sort Algorithm)，排序是将一组数据，依指定的顺序进行排列的过程。

排序的分类

1. 内部排序:
   指将需要处理的所有数据都加载到内部存储器中进行排序。
2. 外部排序法：
   数据量过大，无法全部加载到内存中，需要借助外部存储进行
   排序。

常见的排序算法分类

冒泡排序

冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前向后（从下标较小的元素开始）,依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就象水底下的气泡一样逐渐向上冒。

因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下
来没有进行过交换，就说明序列有序，因此要在排序过程中设置
一个标志flag判断元素是否进行过交换。从而减少不必要的比较。(优化)

第一次排序，最大的会走到最后，以此类推。

代码实现上述推演过程

public class BubbleSort {
    public static void main(String[] args) {
		int arr[] = {3, 9, -1, 10, 20};
		System.out.println("排序前");
		System.out.println(Arrays.toString(arr));
		
		//为了容易理解，我们把冒泡排序的演变过程，给大家展示
		// 第一趟排序，就是将第最大的数排在最后
		
		for (int j = 0; j < arr.length - 1  ; j++) {
			// 如果前面的数比后面的数大，则交换
			if (arr[j] > arr[j + 1]) {
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
		
		System.out.println("第一趟排序后的数组");
		System.out.println(Arrays.toString(arr));
		
		// 第二趟排序，就是将第二大的数排在倒数第二位
		
		for (int j = 0; j < arr.length - 1 - 1 ; j++) {
			// 如果前面的数比后面的数大，则交换
			if (arr[j] > arr[j + 1]) {
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
		
		System.out.println("第二趟排序后的数组");
		System.out.println(Arrays.toString(arr));
		
		// 第三趟排序，就是将第三大的数排在倒数第三位
		
		for (int j = 0; j < arr.length - 1 - 2; j++) {
			// 如果前面的数比后面的数大，则交换
			if (arr[j] > arr[j + 1]) {
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}

		System.out.println("第三趟排序后的数组");
		System.out.println(Arrays.toString(arr));
		
		// 第四趟排序，就是将第4大的数排在倒数第4位
		for (int j = 0; j < arr.length - 1 - 3; j++) {
			// 如果前面的数比后面的数大，则交换
			if (arr[j] > arr[j + 1]) {
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}

		System.out.println("第四趟排序后的数组");
		System.out.println(Arrays.toString(arr)); 
    }
}

核心实现代码

for (int i = 0; i < arr.length - 1; i++) {
	for (int j = 0; j < arr.length - 1 - i; j++) {
		// 如果前面的数比后面的数大，则交换
		if (arr[j] > arr[j + 1]) {
			temp = arr[j];
			arr[j] = arr[j + 1];
			arr[j + 1] = temp;
		}
	}
	System.out.println("第" + (i + 1) + "趟排序后的数组");
	System.out.println(Arrays.toString(arr));
}

代码优化

一个标志flag判断元素是否进行过交换。从而减少不必要的比较

public static void bubbleSort(int[] arr) {
	// 冒泡排序 的时间复杂度 O(n^2), 自己写出
	int temp = 0; // 临时变量
	boolean flag = false; // 标识变量，表示是否进行过交换
	for (int i = 0; i < arr.length - 1; i++) {
		for (int j = 0; j < arr.length - 1 - i; j++) {
			// 如果前面的数比后面的数大，则交换
			if (arr[j] > arr[j + 1]) {
				flag = true;
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
		//System.out.println("第" + (i + 1) + "趟排序后的数组");
		//System.out.println(Arrays.toString(arr));

		if (!flag) { // 在一趟排序中，一次交换都没有发生过
			break;
		} else {
			flag = false; // 重置flag!!!, 进行下次判断
		}
	}
}

测试冒泡排序时间

int[] arr = new int[80000];
for(int i =0; i < 80000;i++) {
	arr[i] = (int)(Math.random() * 8000000); //生成一个[0, 8000000) 数
}

Date data1 = new Date();
SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String date1Str = simpleDateFormat.format(data1);
System.out.println("排序前的时间是=" + date1Str);

//测试冒泡排序
bubbleSort(arr);

Date data2 = new Date();
String date2Str = simpleDateFormat.format(data2);
System.out.println("排序后的时间是=" + date2Str);