排序

排序也称排序算法(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);