[数据结构与算法]Java数据结构Day14--冒泡排序优化

对于冒泡排序,时间复杂度是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);

        /*第一次遍历,要把最大的放到最后面
        int tmp = 0;
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] > arr[i+1]){
                tmp = arr[i+1];
                arr[i + 1] = arr[i];
                arr[i] = tmp;
            }
        }*/

        //原冒泡排序
        /*int tmp = 0;
        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]){
                    tmp = arr[j+1];
                    arr[j + 1] = arr[j];
                    arr[j] = tmp;
                }
            }
        }*/
    }
    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));
    }
}