java的经典排序讲解以及简单优化
java面试中一般都会遇到让你手写三大排序伪代码的场景。
java排序分四类
1、插入排序 直接插入排序 希尔排序 2、交换排序 冒泡排序 快速排序 3、选择排序 简单选择排序 堆排序 快速排序 4、归并排序
面试中，我们面得最多的应该要数冒泡排序了，我们就先来讲讲冒泡排序。
正常情况下，我们进行伪代码的编写，或者需要在电脑上敲出来，冒泡排序是比较经典的排序：下面我们简单实现一下：
我将时间运行时间打印了出来，可能是由于数据量比较少的原因，时间ms显示不出来，我选择单位为ns，可以直观的看出来排序算法效率对比。
public static void main(String[] args) { int[] arr = { 1, 3, 4, 2, 6, 7, 8, 0, 5 }; int i = 0; int tmp = 0; long startTime = System.nanoTime(); // 获取开始时间 for (i = 0; i < arr.length - 1; i++) { // 确定排序趟数 int j = 0; for (j = 0; j < arr.length - 1 - i; j++) { // 确定比较次数 if (arr[j] > arr[j + 1]) { // 交换 tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; } } } long endTime = System.nanoTime(); // 获取结束时间 System.out.println("排序結果:" + Arrays.toString(arr)); System.out.println("程序运行时间： " + (endTime - startTime) + "ns"); }
控制台打印如下：
排序結果:[0, 1, 2, 3, 4, 5, 6, 7, 8] 程序运行时间：3800ns
上述代码是比较两个相邻的数，如果前面的数大于后面的数，则交换位置，重复执行，随着参与比较的元素越来越少，当最后一个元素比较完成时，则排序完成。
但是这样做有一个问题，如果我们的数据前面已经是有序的了，只是在后面才是无序的，比如int[] arr = {0, 1, 2, 3, 4, 6, 7, 8, 5 };
前面5位数都是有序的。这样，我们有一些排序就将是多余的，那么我们应该怎么优化呢，我们可以尝试着立下一个flag，用来标记，判断这一趟排序是否交换元素，如果有序的话我们就没必要进行下去。
优化代码如下：
public static void main(String[] args) { int[] arr = { 1, 3, 4, 2, 6, 7, 8, 0, 5 }; int i = 0; int tmp = 0; long startTime=System.nanoTime(); //获取开始时间 for (i = 0; i < arr.length - 1; i++){ // 确定排序趟数 int j = 0; Boolean flag = true; for (j = 0; j < arr.length - 1 - i; j++){ // 确定比较次数 if (arr[j] > arr[j + 1]){ // 交换 tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; flag = false;// 加入标记 } } if (flag == true) { //未交换元素，结束当前循环，但是外面需要打印，所以这里不用return结束 continue; } } long endTime=System.nanoTime(); //获取结束时间 System.out.println("排序結果:" + Arrays.toString(arr)); System.out.println("程序运行时间： "+(endTime-startTime)+"ns"); }
控制台打印如下：
排序結果:[0, 1, 2, 3, 4, 5, 6, 7, 8] 程序运行时间：3500ns
但是这样我们又会发现一个问题，那就是上述代码对前面无序，而后面有序的数组排列，效率并不客观，那么我们可以标记一个位置，记录上次排序到哪，后面没有排序，后面的顺序则必然是有序的。
再次优化代码如下：
public static void main(String[] args) { int[] arr = { 1, 3, 4, 2, 6, 7, 8, 0, 5 }; int i = 0; int tmp = 0; Boolean flag = true; int pos = 0;// 用来记录最后一次交换的位置 int k = arr.length - 1; long startTime = System.nanoTime(); // 获取开始时间 for (i = 0; i < arr.length - 1; i++) { pos = 0; int j = 0; flag = true; for (j = 0; j < k; j++) { if (arr[j] > arr[j + 1]) { // 交换 tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; flag = false;// 加入标记 pos = j;// 交换元素，记录最后一次交换的位置 } } if (flag == true)// 如果没有交换过元素，则已经有序 { continue; } k = pos;// 下一次比较到记录位置即可 } long endTime = System.nanoTime(); // 获取结束时间 System.out.println("排序結果:" + Arrays.toString(arr)); System.out.println("程序运行时间： " + (endTime - startTime) + "ns"); }
控制台打印如下：
排序結果:[0, 1, 2, 3, 4, 5, 6, 7, 8] 程序运行时间：3001ns
可能是由于数据顺序的问题，差距并不是特别大，冒泡排序适用于数组基本有序的情况，也就是数据本身不是太乱。并且元素不能太多，太多元素前后交换位置还是会有效率问题。
你看完本系列文章，去面试offer又能多2K！！
