Java进阶：搞懂这四大排序算法，面试Offer稳了！

在 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 - i - 1; 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[] arr = {64, 34, 25, 12, 22, 11, 90};
        bubbleSort(arr);
        System.out.println("排序后的数组：");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

实战避坑

• 时间复杂度： 冒泡排序的时间复杂度为 O(n^2)，在数据量较大时效率较低。
• 空间复杂度： 空间复杂度为 O(1)，只需要常量级的额外空间。
• 优化： 可以通过设置一个标志位来判断在一趟排序中是否发生了交换，如果没有发生交换，则说明数组已经有序，可以提前结束排序。例如，在应对高并发场景时，优化后的算法可以减少CPU资源的无效消耗，避免服务器因资源耗尽而宕机，起到一定的“熔断”效果。

选择排序

原理剖析

选择排序的工作原理是：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

代码实现

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[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        selectionSort(arr);
        System.out.println("排序后的数组：");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

实战避坑

• 时间复杂度： 选择排序的时间复杂度始终为 O(n^2)，与输入数据的初始状态无关。
• 空间复杂度： 空间复杂度为 O(1)。
• 适用场景： 当数据量较小，并且对稳定性没有要求时，可以选择选择排序。

插入排序

原理剖析

插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。通常情况下，插入排序从已排序的序列的最后一个元素开始，逐个与新元素进行比较，如果已排序的元素大于新元素，则将已排序的元素后移一位；如果已排序的元素小于等于新元素，则将新元素插入到该位置。

代码实现

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;

            // 将 arr[0...i-1] 中大于 key 的元素向后移动
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        insertionSort(arr);
        System.out.println("排序后的数组：");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

实战避坑

• 时间复杂度： 插入排序在最好情况下（数组已经有序）的时间复杂度为 O(n)，最坏情况下（数组完全逆序）的时间复杂度为 O(n^2)。
• 空间复杂度： 空间复杂度为 O(1)。
• 适用场景： 插入排序对于小型数据集或基本有序的数据集非常有效。在实际应用中，可以结合二分查找优化查找插入位置的过程，提高效率。

快速排序

原理剖析

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

1. 从数列中挑出一个元素，称为 “基准”（pivot）；
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

代码实现

public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);

            quickSort(arr, low, pi - 1);  // 递归排序基准左边的子数组
            quickSort(arr, pi + 1, high); // 递归排序基准右边的子数组
        }
    }

    // 分区函数
    public 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++;

                // 交换 arr[i] 和 arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // 交换 arr[i + 1] 和 arr[high] (pivot)
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return (i + 1);
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        quickSort(arr, 0, arr.length - 1);
        System.out.println("排序后的数组：");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

实战避坑

• 时间复杂度： 快速排序的平均时间复杂度为 O(n log n)，但在最坏情况下（例如，数组已经有序或完全逆序）的时间复杂度为 O(n^2)。
• 空间复杂度： 空间复杂度为 O(log n)，主要是由于递归调用所占用的栈空间。
• 优化： 可以通过随机选择基准值来避免最坏情况的发生。在实际的生产环境中，应对高并发、大数据量的情况，需要考虑避免出现栈溢出的情况，可以考虑使用尾递归优化，或者将递归算法改为迭代算法，甚至可以考虑使用分布式计算框架，例如 Hadoop 的 MapReduce，或者 Spark 来处理大规模数据的排序任务，充分利用集群的计算能力，提高排序的效率和稳定性。同时，在服务器层面，可以使用 Nginx 进行负载均衡，将排序请求分发到不同的服务器上，避免单点故障，提高系统的可用性。Nginx 的反向代理功能可以将客户端的请求转发到后端的多个服务器上，从而实现负载均衡。Nginx 的配置相对简单，可以通过宝塔面板进行可视化操作，方便快捷。同时，可以通过监控 Nginx 的并发连接数，及时发现和解决潜在的性能问题。

掌握这些 Java 学习中的四大排序算法，可以让你在技术道路上更进一步。希望本文能帮助你更好地理解和应用这些算法。