排序算法是编程中的基础核心知识，无论是笔试面试还是实际开发，都离不开对基础排序算法的理解和运用。本文将详细拆解冒泡排序、简单选择排序、插入排序和希尔排序的核心思想、Java 实现代码及特点，帮助初学者快速掌握这四类常用排序算法。

一、冒泡排序：两两对比，逐步 “冒泡”

核心思想

Java代码实现

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {5, 7, 4, 2, 0, 3, 1, 6};
        bubbleSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    public static void bubbleSort(int[] arr) {
        for (int j = 0; j < arr.length; j++) {
            for (int i = 0; i < arr.length - 1; i++) {
                if (arr[i] > arr[i + 1]) {
                    int temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                }
            }
        }
    }
}

算法特点

• 实现逻辑简单，易于理解和编码。
• 时间复杂度为 O (n²)，适用于小规模数据排序。
• 属于稳定排序算法，相等元素的相对位置不会改变。

二、简单选择排序：定位最小，直接交换

核心思想

每一轮遍历未排序部分，找到其中的最小值，将其与未排序部分的第一个元素交换位置。通过不断缩小未排序范围，最终实现数组有序。
Java 实现代码

public class SelectionSort {
    public static void main(String[] args) {
        int[] arr = {5, 7, 4, 2, 0, 3, 1, 6};
        sort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    public static void sort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int minIndex = i;
            // 查找未排序部分的最小值索引
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            // 交换最小值与未排序部分第一个元素
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

算法特点

• 核心在于 “选择” 最小值，交换操作仅需一次 / 轮。
• 时间复杂度为 O (n²)，性能略优于冒泡排序（交换次数更少）。
• 属于不稳定排序算法，可能改变相等元素的相对位置

三、插入排序：逐个插入，构建有序序列

核心思想

将数组分为有序部分和无序部分，初始时有序部分仅包含第一个元素。依次将无序部分的元素插入到有序部分的合适位置，逐步扩大有序范围直至整个数组有序。

Java 实现代码

public class InsertionSort {
    public static void main(String[] args) {
        int[] arr = {5, 7, 4, 2, 0, 3, 1, 6};
        sort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    public static void sort(int[] arr) {
        for (int j = 1; j < arr.length; j++) {
            // 从有序部分末尾向前对比，找到插入位置
            for (int i = j - 1; i >= 0; i--) {
                if (arr[i] > arr[i + 1]) {
                    int temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                }
            }
        }
    }
}

算法特点

• 适用于接近有序的数据，此时时间复杂度接近 O (n)。
• 空间复杂度为 O (1)，属于原地排序算法。
• 缺点是插入值越小时，元素后移次数越多，效率降低。
• 属于稳定排序算法。

四、希尔排序：分组插入，缩小增量

核心思想

希尔排序又称 “缩小增量排序”，是插入排序的优化版。通过设定增量将数组分组，对每组进行插入排序；逐步缩小增量，重复分组和排序操作；最终增量为 1 时，对整个数组进行一次插入排序，完成最终排序。

Java 实现代码

1. 增量为数组长度的一半（两两分组）

public class ShellSort {
    public static void main(String[] args) {
        int[] arr = {5, 7, 4, 2, 0, 3, 1, 6};
        sort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    public static void sort(int[] arr) {
        // 增量为 4（数组长度 8 的一半）
        for (int j = 4; j < arr.length; j++) {
            for (int i = j - 4; i >= 0; i -= 4) {
                if (arr[i] > arr[i + 4]) {
                    int temp = arr[i];
                    arr[i] = arr[i + 4];
                    arr[i + 1] = temp;
                }
            }
        }
    }
}

2. 增量为数组长度的四分之一（四组分组）

public class ShellSort {
    public static void main(String[] args) {
        int[] arr = {5, 7, 4, 2, 0, 3, 1, 6};
        sort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    public static void sort(int[] arr) {
        // 增量为 2（数组长度 8 的四分之一）
        for (int j = 2; j < arr.length; j++) {
            for (int i = j - 2; i >= 0; i -= 2) {
                if (arr[i] > arr[i + 2]) {
                    int temp = arr[i];
                    arr[i] = arr[i + 2];
                    arr[i + 1] = temp;
                }
            }
        }
    }
}

算法特点

• 通过分组排序减少元素移动次数，效率优于直接插入排序。
• 时间复杂度与增量选择相关，平均时间复杂度为 O (n log n)。
• 属于不稳定排序算法，空间复杂度为 O (1)。
• 核心是 “先让数组整体接近有序，再进行最终排序”。

总结

本文介绍的四种排序算法各有优劣，适用场景不同：

• 冒泡排序：适合入门学习，小规模数据简单排序场景。
• 简单选择排序：减少了交换次数，比冒泡排序更高效。
• 插入排序：适合接近有序的数据，实际应用中表现较好。
• 希尔排序：插入排序的优化版，适合中大规模数据排序。

掌握这些基础排序算法的核心逻辑和实现细节，能为后续学习更复杂的排序算法（如快速排序、归并排序）打下坚实基础。