昨天给大家讲解了 Java 玩转冒泡排序，大家一定觉得并没有什么难度吧，不知道大佬们玩转了吗？不知道大家有没有多加思考，实际上在我们最后的一种思路上，还可以再继续改进。
我们先看看昨天最终版本的代码。
public class Test09 { private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } private static void printArr(int[] arr) { for (int anArr : arr) { System.out.print(anArr + " "); } } private static void bubbleSort(int[] arr) { if (arr == null) return; // 定义一个标记 isSort，当其值为 true 的时候代表已经有序。 boolean isSort; for (int i = 0; i < arr.length - 1; i++) { isSort = true; for (int j = 1; j < arr.length - i; j++) { if (arr[j - 1] > arr[j]) { swap(arr, j - 1, j); isSort = false; } } if (isSort) break; } } public static void main(String[] args) { int[] arr = {6, 4, 2, 1, 8, 3, 7, 9, 5}; bubbleSort(arr); printArr(arr); } }我们用一个 boolean 变量 isSort 来判断是否已经排序完成，当一整趟遍历都没有发生数据交换的时候，说明已经排序完成，直接 break 退出循环即可。
我们试想一下这样的场景：假设有 100 个数字的数组，仅仅前 10 个无序，后面 90 个均有序并且都大于前面 10 个数字。
我们采用上面的终极算法可以明显看到，第一趟排序后，最后发生交换的位置必定大于 10，且这个位置之后的数据必定已经有序了，但我们还是会去做徒劳的 90 次遍历，而且我们还要遍历 10 次！
显然我们可以找到这样的思路，在第一次排序后，就记住最后发生交换的位置，第二次只要从数组头部遍历到这个位置就 OK 了。
我们不妨直接看看代码实现：
public class Test09 { private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } private static void printArr(int[] arr) { for (int anArr : arr) { System.out.print(anArr + " "); } } private static void bubbleSort(int[] arr) { if (arr == null) return; int flag = arr.length; int k; for (int i = 0; i < arr.length - 1; i++) { k = flag; flag = 0; for (int j = 1; j < k; j++) { if (arr[j - 1] > arr[j]) { swap(arr, j - 1, j); flag = j; } } if (flag == 0) break; } } public static void main(String[] args) { int[] arr = {6, 4, 1, 2, 3, 5, 7, 8, 9}; bubbleSort(arr); printArr(arr); } }其实算法也就那么一回事儿，用心去理解它的原理，理解后，无论是用哪种语言实现起来都是非常简单的。那我们今天就来看看另外两种排序，选择排序和插入排序。
选择排序选择排序（Selection sort）是一种简单直观的排序算法。选择排序之所以叫选择排序就是在一次遍历过程中找到最小元素的角标位置，然后把它放到数组的首端。我们排序过程都是在寻找剩余数组中的最小元素，所以就叫做选择排序。
它的思想如下：
从待排序序列中，找到关键字最小的元素；起始假定第一个元素为最小
如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；
从余下的 N - 1 个元素中，找出关键字最小的元素，重复1，2步，直到排序结束。