冒泡排序

一、简单的冒泡排序算法的实现

package BubbleSort;

import MergeSort.ArrayGenerator;
import MergeSort.SortingHelper;

/**
 * @author DBC
 * @version 1.0
 * @date 2022-02-12 13:49
 */
public class BubbleSort {
    private BubbleSort() {
    }

    public static <E extends Comparable<E>> void sort(E[] data) {
        for (int i = 0; i + 1 < data.length; i++) {
            // arr[n - i,n)已排好序
            // 通过冒泡在 arr[n - i -1] 位置放上合适的元素
            for (int j = 0; j < data.length - i - 1; j++) {
                if (data[j].compareTo(data[j + 1]) > 0) {
                    swap(data, j, j + 1);
                }
            }
        }
    }

    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    public static void main(String[] args) {
        int n = 20000;
        Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
        SortingHelper.sortTest("BubbleSort",arr);
    }
}

二、冒泡排序算法的优化

温馨提示

优化思想：在已经排好序的情况下，我们可不可以直接进行跳过，不要再继续循环了呢？让我们来看看吧[aru_22]

    public static <E extends Comparable<E>> void sort2(E[] data) {
        for (int i = 0; i + 1 < data.length; i++) {
            // arr[n - i,n)已排好序
            // 通过冒泡在 arr[n - i -1] 位置放上合适的元素
            boolean isSwapped = false;

            for (int j = 0; j < data.length - i - 1; j++) {
                if (data[j].compareTo(data[j + 1]) > 0) {
                    swap(data, j, j + 1);
                    isSwapped = true;
                }
            }
            if (!isSwapped){
                break;
            }
        }
    }

温馨提示

我们以长度为：30000的数组来说明一下，可以看到在随机的数组中，优化的数组也会好一些，在完全有序的数组下，这个冒泡排序算法甚至直接进化成为了O(n)级别的算法，是不是挺有意思的，哈哈哈！[aru_42]

三、冒泡排序算法还能继续优化！

温馨提示

设计思想，我们在排序的时候，是可以确定后面的数一定是排好序的，就如上图所示，这样其实我们是可以直接跳过继续很多轮循环的，让我们来看看如何实现！

    public static <E extends Comparable<E>> void sort3(E[] data) {
        for (int i = 0; i + 1 < data.length;) {
            // arr[n - i,n)已排好序
            // 通过冒泡在 arr[n - i -1] 位置放上合适的元素
            int  lastSwappedIndex = 0;
            for (int j = 0; j < data.length - i - 1; j++) {
                if (data[j].compareTo(data[j + 1]) > 0) {
                    swap(data, j, j + 1);
                    lastSwappedIndex = j + 1;
                }
            }
            i = data.length - lastSwappedIndex;
        }
    }

老规矩，依然是同类对比！

    public static void main(String[] args) {
        int n = 30000;
        Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
        Integer[] arr2 = Arrays.copyOf(arr,arr.length);
        Integer[] arr3 = Arrays.copyOf(arr,arr.length);
        SortingHelper.sortTest("BubbleSort",arr);
        SortingHelper.sortTest("BubbleSort2",arr2);
        SortingHelper.sortTest("BubbleSort3",arr3);

        arr = ArrayGenerator.generateOrderedArray(n);
        arr2 = Arrays.copyOf(arr,arr.length);
        arr3 = Arrays.copyOf(arr,arr.length);
        SortingHelper.sortTest("BubbleSort",arr);
        SortingHelper.sortTest("BubbleSort2",arr2);
        SortingHelper.sortTest("BubbleSort3",arr3);
    }

温馨提示

可以看到，我们的算法还有有那么一定的优化的！嘻嘻[aru_41]