对于冒泡排序,时间复杂度是O(n^2),所以可见,在n比较小的场景下,它的效率明显是更高的
我们还可以通过一个boolean值,来判断在这次循环中,有没有变量被更换位置,如果没有,说明后面的顺序都已经调整好,可以直接跳出循环.可以减少循环次数(效率有限)
拓展:在Hadoop的MapReduce任务中,我们是使用到了一次快排和两次归并排序,这两种排序对于大体量的排序效果较好(后期会写).快排对于全局无序的效率更高;归并对于分区内有序,分区间无序的效率更高.
整体代码import java.util.Arrays; import java.util.Random; public class BubbleSort { public static void main(String[] args) { int[] arr = new int[]{6,9,-7,3,2,8}; sort(arr); //测试一下,假如说有一个8w长度的数组 int[] arr1 = new int[80000]; Random random = new Random(); for (int i = 0; i < arr1.length; i++) { arr1[i] = random.nextInt(80000); } long start = System.currentTimeMillis(); sort(arr1); long end = System.currentTimeMillis(); System.out.println((end - start) / 1000); //原冒泡排序 } public static void sort(int[] arr){ //优化冒泡排序 int count = 0; int tmp = 0; for (int i = 0; i < arr.length - 1; i++) { boolean flag = false; for (int j = 0; j < arr.length - 1 - i; j++) { if (arr[j] > arr[j+1]){ flag = true; tmp = arr[j+1]; arr[j + 1] = arr[j]; arr[j] = tmp; } } count++; if (!flag){ break; } } System.out.println("经历了" + count +" 次排序后"+ Arrays.toString(arr)); } }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)