Java排序算法全解析：从冒泡到快速排序，案例实操

2026-01-05 02:32

排序，是算法中最基础、最常用的操作之一。无论是数据分析、搜索优化，还是系统设计，掌握常见排序算法都是 Java 程序员的必修课。本篇文章将结合 Java 代码，带你从基础的冒泡排序，到高效的快速排序，全面理解各种排序算法。

1️⃣ 冒泡排序（Bubble Sort）

冒泡排序是最简单直观的排序算法，它重复地遍历数组，每次比较相邻的两个元素，如果顺序错误就交换。大体思想就像水泡从底部往上冒。

特点：

时间复杂度：O(n²)
空间复杂度：O(1)
稳定排序

Java实现

java

复制代码

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

    public static void main(String[] args) {
        int[] data = {5, 3, 8, 4, 2};
        bubbleSort(data);
        System.out.println(Arrays.toString(data));
    }
}

✅ 输出：

plaintext

复制代码

[2, 3, 4, 5, 8]

注意点：

冒泡排序适合小数据量。
可以通过增加一个 flag 判断是否提前结束优化。

2️⃣ 选择排序（Selection Sort）

选择排序每次从未排序的部分选出最小（或最大）的元素，放到已排序部分的末尾。

特点：

时间复杂度：O(n²)
空间复杂度：O(1)
不稳定排序

Java实现

java

复制代码

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }

    public static void main(String[] args) {
        int[] data = {5, 3, 8, 4, 2};
        selectionSort(data);
        System.out.println(Arrays.toString(data));
    }
}

✅ 输出：

plaintext

复制代码

[2, 3, 4, 5, 8]

注意点：

虽然时间复杂度和冒泡相同，但交换次数更少。
大数据量下仍然效率低下。

3️⃣ 插入排序（Insertion Sort）

插入排序类似整理扑克牌，把每张牌插入到前面已排序的部分中。

特点：

时间复杂度：O(n²)，近乎有序时可降到 O(n)
空间复杂度：O(1)
稳定排序

Java实现

java

复制代码

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] data = {5, 3, 8, 4, 2};
        insertionSort(data);
        System.out.println(Arrays.toString(data));
    }
}

✅ 输出：

plaintext

复制代码

[2, 3, 4, 5, 8]

注意点：

对近乎有序的数据非常高效。
插入排序思想是很多高级排序的基础。

4️⃣ 快速排序（Quick Sort）

快速排序是分治算法的代表，选一个“基准”，把数组分成比基准小的和比基准大的两部分，再递归排序。

特点：

时间复杂度：O(n log n) 平均
最坏情况：O(n²)
空间复杂度：O(log n) 递归栈
不稳定排序

Java实现

java

复制代码

public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(arr, low, high);
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        return i + 1;
    }

    public static void main(String[] args) {
        int[] data = {5, 3, 8, 4, 2};
        quickSort(data, 0, data.length - 1);
        System.out.println(Arrays.toString(data));
    }
}

✅ 输出：

plaintext

复制代码

[2, 3, 4, 5, 8]

注意点：

快速排序效率高，适合大部分数据。
避免选择最小或最大元素为基准，否则退化为 O(n²)。

5️⃣ 归并排序（Merge Sort）

归并排序也是分治算法，把数组分成两半，排序后合并。

特点：

时间复杂度：O(n log n)
空间复杂度：O(n)
稳定排序

Java实现

java

复制代码

public class MergeSort {
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;

        while (i <= mid && j <= right) {
            temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
        }

        while (i <= mid) temp[k++] = arr[i++];
        while (j <= right) temp[k++] = arr[j++];

        for (int l = 0; l < temp.length; l++) {
            arr[left + l] = temp[l];
        }
    }

    public static void main(String[] args) {
        int[] data = {5, 3, 8, 4, 2};
        mergeSort(data, 0, data.length - 1);
        System.out.println(Arrays.toString(data));
    }
}

✅ 输出：

plaintext

复制代码

[2, 3, 4, 5, 8]

注意点：

稳定且适合大数据排序。
需要额外空间存放临时数组。

6️⃣ 小结

排序算法	时间复杂度	空间复杂度	稳定性	适用场景
冒泡排序	O(n²)	O(1)	稳定	小数据量，学习算法原理
选择排序	O(n²)	O(1)	不稳定	小数据量，交换少
插入排序	O(n²)	O(1)	稳定	数据近乎有序
快速排序	O(n log n)	O(log n)	不稳定	大部分数据，高效
归并排序	O(n log n)	O(n)	稳定	大数据，要求稳定排序