常见排序算法及优化实现（Java 版）

目录

前置准备

排序算法

冒泡排序版本 I

冒泡排序版本 II

选择排序版本 I

选择排序版本 II

插入排序版本 I

插入排序版本 II

希尔排序版本 I

快速排序版本 I

归并排序版本 I

堆排序版本 I

JDK Arrays.sort()

效率对比

前置准备

定义一个只有 sort 方法的接口

public interface SortExecutor {

    /**
     * 排序数组
     *
     * @param nums 待排序的数组
     */
    void sort(int[] nums);

    /**
     * 校验数组是否需要排序
     *
     * @param nums 待校验的数组
     */
    default boolean checkNumsEmpty(int[] nums) {
        return nums == null || nums.length == 0;
    }

}

定义一个 DataHelper 用于生成随机数据和数据处理

public class DataHelper {

    /**
     * 生成固定大小、固定范围的随机整数数组
     *
     * @param generateCount 需要生成的数量
     * @return 随机整数数组
     */
    public static int[] generateRandomNumsByCount(int generateCount) {
        int[] randomNums = new int[generateCount];
        Random random = new Random();

        for (int i = 0; i < generateCount; i++) {
            // [0, generateCount]
            randomNums[i] = random.nextInt(generateCount + 1);
        }

        return randomNums;
    }

    /**
     * 交换数组中的两个索引位置的元素
     *
     * @param arr  数组
     * @param src  来源位置
     * @param dest 目的位置
     */
    public static void swapTwoElementInArray(int[] arr, int src, int dest) {
        int temp = arr[src];
        arr[src] = arr[dest];
        arr[dest] = temp;
    }

}

排序算法

冒泡排序版本 I

public class BubbleSortV1Executor implements SortExecutor {

    /**
     * 冒泡排序版本 I
     * 思路：将数组中相邻元素从前往后依次进行比较，如果前一个元素比后一个元素大则交换，每一轮循环最大元素就在数组末尾。
     * 时间复杂度：O(N²) 内外两层循环，N 是 nums 的长度
     * 空间复杂度：O(1)
     *
     * @param nums 待排序的数组
     */
    @Override
    public void sort(int[] nums) {
        if (checkNumsEmpty(nums)) {
            return;
        }
        int numsLen = nums.length;

        for (int i = 0; i < numsLen - 1; i++) {
            for (int j = 0; j < numsLen - 1; j++) {
                if (nums[j + 1] >= nums[j]) {
                    continue;
                }
                DataHelper.swapTwoElementInArray(nums, j, j + 1);
            }
        }
    }

}

冒泡排序版本 II

public class BubbleSortV2Executor implements SortExecutor {

    /**
     * 冒泡排序版本 II
     * 优化点：添加一个标识用来确定内层排序是否存在交换元素的动作，没有则说明数组已经有序。
     * 时间复杂度：最差为O(N²)，取决于随机数组的数据分布特点。
     * 空间复杂度：O(1)
     *
     * @param nums 待排序的数组
     */
    @Override
    public void sort(int[] nums) {
        if (checkNumsEmpty(nums)) {
            return;
        }
        int numsLen = nums.length;

        for (int i = 0; i < numsLen - 1; i++) {
            boolean isExistSwap = false;
            // 减去 i 是因为之前的循环已经排过序了
            for (int j = 0; j < numsLen - 1 - i; j++) {
                if (nums[j + 1] >= nums[j]) {
                    continue;
                }
                isExistSwap = true;
                DataHelper.swapTwoElementInArray(nums, j, j + 1);
            }
            if (!isExistSwap) {
                return;
            }
        }
    }

}

选择排序版本 I

public class SelectSortV1Executor implements SortExecutor {

    /**
     * 选择排序版本 I
     * 思路：将数组分为前边已排序和后边未排序的两部分，在未排序序列中找到最小元素，存放到排序序列的末尾。
     * 时间复杂度：O(N²) 内外两层循环，N 是 nums 的长度。
     * 空间复杂度：O(1)
     *
     * @param nums 待排序的数组
     */
    @Override
    public void sort(int[] nums) {
        if (checkNumsEmpty(nums)) {
            return;
        }
        int numsLen = nums.length;

        for (int i = 0; i < numsLen - 1; i++) {
            int minNumIndex = i;

            for (int j = i + 1; j < numsLen; j++) {
                if (nums[j] >= nums[minNumIndex]) {
                    continue;
                }
                minNumIndex = j;
            }
            DataHelper.swapTwoElementInArray(nums, i, minNumIndex);
        }
    }

}

选择排序版本 II

public class SelectSortV2Executor implements SortExecutor {

    /**
     * 选择排序版本 II
     * 优化点：每一轮同时找出最小值和最大值，分别放在队首和队尾，理论上循环次数可减半。
     * 时间复杂度：O(N²)，最坏情况为 N/2 次循环。
     * 空间复杂度：O(1)
     *
     * @param nums 待排序的数组
     */
    @Override
    public void sort(int[] nums) {
        if (checkNumsEmpty(nums)) {
            return;
        }
        int numsLen = nums.length;
        int leftIndex = 0;
        int rightIndex = numsLen - 1;

        while (leftIndex < rightIndex) {
            int minNumIndex = leftIndex;
            int maxNumIndex = rightIndex;

            for (int i = leftIndex; i <= rightIndex; i++) {
                if (nums[i] < nums[minNumIndex]) {
                    minNumIndex = i;
                }
                if (nums[i] > nums[maxNumIndex]) {
                    maxNumIndex = i;
                }
            }
            DataHelper.swapTwoElementInArray(nums, maxNumIndex, rightIndex);
            // 需要考虑 minNumIndex == maxNumIndex 的情况
            if (minNumIndex == rightIndex) {
                minNumIndex = maxNumIndex;
            }
            DataHelper.swapTwoElementInArray(nums, minNumIndex, leftIndex);
            leftIndex++;
            rightIndex--;
        }
    }

}

插入排序版本 I

public class InsertSortV1Executor implements SortExecutor {

    /**
     * 插入排序版本 I
     * 思路：将数组分为前边已排序和后边未排序的两部分，依次将未排序部分的元素插入到排序序列的指定位置。
     * 时间复杂度：O(N²) 内外两层循环，N 是 nums 的长度。
     * 空间复杂度：O(1)
     *
     * @param nums 待排序的数组
     */
    @Override
    public void sort(int[] nums) {
        if (checkNumsEmpty(nums)) {
            return;
        }
        int numsLen = nums.length;

        for (int i = 1; i < numsLen; i++) {
            // 未排序部分的元素在排序部分 从右往左 找到属于自己的位置
            for (int j = i - 1; j >= 0 && nums[j] > nums[j + 1]; j--) {
                DataHelper.swapTwoElementInArray(nums, j, j + 1);
            }
        }
    }

}

插入排序版本 II

public class InsertSortV2Executor implements SortExecutor {

    /**
     * 插入排序版本 II
     * 优化点：将比较过程改为二分法
     * 时间复杂度：O(N * log N) 外层循环 * 内层二分查找，N 是 nums 的长度。
     * 空间复杂度：O(1)
     *
     * @param nums 待排序的数组
     */
    @Override
    public void sort(int[] nums) {
        if (checkNumsEmpty(nums)) {
            return;
        }
        int numsLen = nums.length;

        for (int i = 1; i < numsLen; i++) {
            int leftIndex = 0;
            int rightIndex = i - 1;
            int curNum = nums[i];

            while (leftIndex <= rightIndex) {
                int midIndex = leftIndex + (rightIndex - leftIndex) / 2;
                if (nums[midIndex] > curNum) {
                    rightIndex = midIndex - 1;
                } else {
                    leftIndex = midIndex + 1;
                }
            }
            // 需要将所有元素往右移一位
            int j;

            for (j = i - 1; j >= rightIndex + 1; j--) {
                nums[j + 1] = nums[j];
            }
            nums[j + 1] = curNum;
        }
    }

}

希尔排序版本 I

public class ShellSortV1Executor implements SortExecutor {

    /**
     * 希尔排序版本 I
     * 思路：类似于插入排序，在此基础上设置 increment 间隔作为逻辑分组
     * 时间复杂度：O(N * log N) ~ O(N²) 取决于 increment 的选取
     * 空间复杂度：O(1)
     *
     * @param nums 待排序的数组
     */
    @Override
    public void sort(int[] nums) {
        if (checkNumsEmpty(nums)) {
            return;
        }
        int numsLen = nums.length;
        int increment = numsLen;

        while (increment > 1) {
            // 自定义
            increment = increment / 3 + 1;
            // 对每个按增量划分后的逻辑分组，进行插入排序
            for (int i = increment; i < numsLen; i++) {
                if (nums[i - increment] > nums[i]) {
                    int curNum = nums[i];
                    int j = i - increment;

                    while (j >= 0 && nums[j] > curNum) {
                        nums[j + increment] = nums[j];
                        j -= increment;
                    }
                    nums[j + increment] = curNum;
                }
            }
        }
    }

}

快速排序版本 I

public class QuickSortV1Executor implements SortExecutor {

    /**
     * 快速排序版本 I
     * 思路：每趟排序时选出一个基准值，然后将所有元素与该基准值比较，并按大小分成左右两部分，递归执行该过程，直到所有元素都完成排序。
     * 时间复杂度：O(N * log N) N 为数组的长度
     * 空间复杂度：O(N * log N) 递归调用所消耗的栈空间
     *
     * @param nums 待排序的数组
     */
    @Override
    public void sort(int[] nums) {
        if (checkNumsEmpty(nums)) {
            return;
        }
        int leftBoundary = 0;
        int rightBoundary = nums.length - 1;

        quickSort(nums, leftBoundary, rightBoundary);
    }

    private void quickSort(int[] nums, int leftBoundary, int rightBoundary) {
        if (leftBoundary > rightBoundary) {
            return;
        }
        int leftIndex = leftBoundary;
        int rightIndex = rightBoundary;
        // 选取一个基准值 pivot，小于 pivot 的元素在左边，大于 pivot 的元素在右边。
        int pivot = nums[leftIndex];

        while (leftIndex < rightIndex) {
            // 从右往左找一个小于 pivot 的数
            while (pivot <= nums[rightIndex] && leftIndex < rightIndex) {
                rightIndex--;
            }
            // 从左往右找一个大于 pivot 的数
            while (pivot >= nums[leftIndex] && leftIndex < rightIndex) {
                leftIndex++;
            }
            if (leftIndex < rightIndex) {
                DataHelper.swapTwoElementInArray(nums, leftIndex, rightIndex);
            }
        }
        // 中间这个数放左边
        nums[leftBoundary] = nums[leftIndex];
        // pivot 放中间
        nums[leftIndex] = pivot;
        // 递归中间数的左右部分
        quickSort(nums, leftBoundary, leftIndex - 1);
        quickSort(nums, rightIndex + 1, rightBoundary);
    }

}

归并排序版本 I

public class MergeSortV1Executor implements SortExecutor {

    /**
     * 归并排序版本 I
     * 思路：分而治之，拆分成最小排序单元后进行组合
     * 时间复杂度：O(N * log N) N 为数组的长度
     * 空间复杂度：O(N) tempNums 所占用的空间
     *
     * @param nums 待排序的数组
     */
    @Override
    public void sort(int[] nums) {
        if (checkNumsEmpty(nums)) {
            return;
        }
        int numsLen = nums.length;
        int[] tempNums = new int[numsLen];

        mergeSort(nums, 0, numsLen - 1, tempNums);
    }

    private void mergeSort(int[] nums, int leftBoundary, int rightBoundary, int[] tempNums) {
        if (leftBoundary == rightBoundary) {
            return;
        }
        int midIndex = leftBoundary + (rightBoundary - leftBoundary) / 2;
        mergeSort(nums, leftBoundary, midIndex, tempNums);
        mergeSort(nums, midIndex + 1, rightBoundary, tempNums);
        // 如果合并完 mid 小于右边则说明当次合并已经有序
        if (nums[midIndex] <= nums[midIndex + 1]) {
            return;
        }

        for (int i = leftBoundary; i <= rightBoundary; i++) {
            tempNums[i] = nums[i];
        }
        // 对 tempNums 进行分区 [leftBoundary, midIndex] [midIndex + 1, rightBoundary]
        int leftIndex = leftBoundary;
        int rightIndex = midIndex + 1;
        // 分区比较
        for (int i = leftBoundary; i <= rightBoundary; i++) {
            if (leftIndex == midIndex + 1) {
                nums[i] = tempNums[rightIndex++];
            } else if (rightIndex == rightBoundary + 1) {
                nums[i] = tempNums[leftIndex++];
            } else if (tempNums[leftIndex] >= tempNums[rightIndex]) {
                nums[i] = tempNums[rightIndex++];
            } else if (tempNums[leftIndex] < tempNums[rightIndex]) {
                nums[i] = tempNums[leftIndex++];
            }
        }
    }

}

堆排序版本 I

public class HeapSortV1Executor implements SortExecutor {

    /**
     * 堆排序版本 I
     * 思路：利用大顶堆性质，每一轮将大顶堆的第一个元素放到未排序数组尾部
     * 时间复杂度：O(N * log N) N 为数组的长度
     * 空间复杂度：O(1)
     *
     * @param nums 待排序的数组
     */
    @Override
    public void sort(int[] nums) {
        if (checkNumsEmpty(nums)) {
            return;
        }
        int numsLen = nums.length;
        // 从最后一颗子树开始往前建大顶堆
        for (int i = numsLen / 2 - 1; i >= 0; i--) {
            heapSort(nums, numsLen, i);
        }
        // 排序
        for (int i = numsLen - 1; i > 0; i--) {
            DataHelper.swapTwoElementInArray(nums, i, 0);
            heapSort(nums, i, 0);
        }
    }

    private void heapSort(int[] nums, int numsLen, int index) {
        // 记录最大值的索引
        int maxNumIndex = index;
        int leftIndex = index * 2 + 1;
        int rightIndex = index * 2 + 2;
        // 维护大顶堆
        if (leftIndex < numsLen && nums[maxNumIndex] < nums[leftIndex]) {
            maxNumIndex = leftIndex;
        }
        if (rightIndex < numsLen && nums[maxNumIndex] < nums[rightIndex]) {
            maxNumIndex = rightIndex;
        }
        if (maxNumIndex != index) {
            DataHelper.swapTwoElementInArray(nums, index, maxNumIndex);
            heapSort(nums, numsLen, maxNumIndex);
        }
    }

}

JDK Arrays.sort()

public class JDKSortExecutor implements SortExecutor {

    /**
     * JDK Arrays 工具类的内置排序
     *
     * @param nums 待排序的数组
     */
    @Override
    public void sort(int[] nums) {
        if (checkNumsEmpty(nums)) {
            return;
        }
        Arrays.sort(nums);
    }

}

效率对比

定义执行器枚举类并在 SortExecutorManager 中完成所有 SortExecutor 实现类的注册

SortExecutorEnum

public enum SortExecutorEnum {

    BUBBLE_SORT_V1("Bubble Sort Version I", new BubbleSortV1Executor()),
    BUBBLE_SORT_V2("Bubble Sort Version II", new BubbleSortV2Executor()),
    SELECT_SORT_V1("Select Sort Version I", new SelectSortV1Executor()),
    SELECT_SORT_V2("Select Sort Version II", new SelectSortV2Executor()),
    INSERT_SORT_V1("Insert Sort Version I", new InsertSortV1Executor()),
    INSERT_SORT_V2("Insert Sort Version II", new InsertSortV2Executor()),
    SHELL_SORT_V1("Shell Sort Version I", new ShellSortV1Executor()),
    QUICK_SORT_V1("Quick Sort Version I", new QuickSortV1Executor()),
    MERGE_SORT_V1("Merge Sort Version I", new MergeSortV1Executor()),
    HEAP_SORT_V1("Heap Sort Version I", new HeapSortV1Executor()),
    JDK_SORT("JDK Sort", new JDKSortExecutor());

    private final String executorName;

    private final SortExecutor executor;

    SortExecutorEnum(String executorName, SortExecutor executor) {
        this.executorName = executorName;
        this.executor = executor;
    }

    public String getExecutorName() {
        return this.executorName;
    }

    public SortExecutor getExecutor() {
        return this.executor;
    }

}

SortExecutorManager 

public class SortExecutorManager {

    private static final Map<String, SortExecutor> SORT_EXECUTOR_MANAGER;

    static {
        // 初始化并注册所有排序执行器，使用 LinkedHashMap 保证注册顺序
        SORT_EXECUTOR_MANAGER = new LinkedHashMap<>();
        registerSortExecutors();
    }

    private static void registerSortExecutors() {
        // 使用枚举类手动注册，Spring 工程可以使用依赖注入
        SortExecutorEnum[] executorEnums = SortExecutorEnum.values();

        for (SortExecutorEnum executorEnum : executorEnums) {
            SORT_EXECUTOR_MANAGER.put(executorEnum.getExecutorName(), executorEnum.getExecutor());
        }
    }

    public static Map<String, SortExecutor> getSortExecutorManager() {
        return SORT_EXECUTOR_MANAGER;
    }

}

SortApplication

public class SortApplication {
    public static void main(String[] args) {
        Map<String, SortExecutor> sortExecutorManager = SortExecutorManager.getSortExecutorManager();
        int[] randomNums = DataHelper.generateRandomNumsByCount(NUMBER_100_000);
        Set<String> allSortExecutorNames = sortExecutorManager.keySet();

        for (String executorName : allSortExecutorNames) {
            long startTimestamp = System.currentTimeMillis();
            int[] copyRandomNums = Arrays.copyOf(randomNums, randomNums.length);
            sortExecutorManager.get(executorName).sort(copyRandomNums);
//            System.out.println(Arrays.toString(copyRandomNums));
            long endTimestamp = System.currentTimeMillis();
            computeAndPrintDuration(executorName, startTimestamp, endTimestamp);
        }
    }

    private static void computeAndPrintDuration(String executorName, long startTimestamp, long endTimestamp) {
        System.out.println(executorName + " ==> " + (endTimestamp - startTimestamp) + " ms");
    }

}

测试机：MacBook Pro 2023 款

运行结果：

Bubble Sort Version I ==> 14636 ms
Bubble Sort Version II ==> 11860 ms
Select Sort Version I ==> 4471 ms
Select Sort Version II ==> 2363 ms
Insert Sort Version I ==> 3342 ms
Insert Sort Version II ==> 1507 ms
Shell Sort Version I ==> 11 ms
Quick Sort Version I ==> 26 ms
Merge Sort Version I ==> 21 ms
Heap Sort Version I ==> 10 ms
JDK Sort ==> 22 ms