冒泡排序

DBC 1.3K 0

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

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;
            }
        }
    }

冒泡排序插图2

温馨提示

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

冒泡排序插图4

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

冒泡排序插图6

温馨提示

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

    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);
    }

冒泡排序插图8

温馨提示

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

发表评论 取消回复
表情 图片 链接 代码

分享