后端架构师带你彻底掌握七大排序算法：原理、实战与避坑指南

在后端架构设计中，数据处理是核心环节。而七大排序算法作为基础的数据处理工具，对于优化系统性能至关重要。无论是百万级用户的电商平台，还是高并发的在线游戏，高效的排序算法都能显著提升用户体验。例如，在电商搜索场景中，商品按照销量、价格等维度排序，背后就离不开排序算法的支持。如果排序效率低下，在高并发场景下，可能会导致 CPU 飙升，甚至引发 Nginx 出现 502 错误。

排序算法的分类

通常，我们把排序算法分为以下几类：

• 比较类排序：通过比较元素之间的大小来决定元素的相对顺序，常见的有冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序等。
• 非比较类排序：不通过比较来决定元素的顺序，而是利用元素本身的特性，例如计数排序、基数排序等。

本文将重点介绍七大常用的比较类排序算法。

冒泡排序 (Bubble Sort)

原理

冒泡排序是最简单的排序算法之一。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

代码实现 (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]) {
                    // 交换 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)，效率较低，不适合处理大规模数据。在实际应用中，除非数据量很小，或者对性能要求不高，否则应该避免使用冒泡排序。

选择排序 (Selection Sort)

原理

选择排序是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（或最大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。

代码实现 (Java)

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

            // 交换找到的最小元素与 arr[i]
            int temp = arr[min_idx];
            arr[min_idx] = 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)，与冒泡排序类似，不适合处理大规模数据。虽然在某些情况下，选择排序的性能可能略优于冒泡排序，但总体来说，它们都不是高效的排序算法。

插入排序 (Insertion Sort)

原理

插入排序的工作方式是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用 in-place 排序（即只需用到 O(1) 的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

代码实现 (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;

            /* 将 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^2)，但在数据基本有序的情况下，性能会接近 O(n)。因此，插入排序适合处理小规模或者基本有序的数据。在一些复杂的排序算法中，例如希尔排序，也会用到插入排序作为子算法。

希尔排序 (Shell Sort)

原理

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

代码实现 (Java)

public class ShellSort {
    public static void shellSort(int[] arr) {
        int n = arr.length;
        for (int gap = n / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < n; i++) {
                for (int j = i; j >= gap && arr[j - gap] > arr[j]; j -= gap) {
                    int temp = arr[j];
                    arr[j] = arr[j - gap];
                    arr[j - gap] = temp;
                }
            }
        }
    }

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

避坑经验

希尔排序的时间复杂度取决于增量序列的选择，最好情况下可以达到 O(n log n)，但最坏情况下仍然是 O(n^2)。增量序列的选择对希尔排序的性能影响很大，常见的增量序列有 Hibbard 增量序列、Sedgewick 增量序列等。在实际应用中，可以根据数据规模和特点选择合适的增量序列。

归并排序 (Merge Sort)

原理

归并排序是一种基于分治思想的排序算法。它的基本思想是：将待排序序列递归地分成两个子序列，分别对子序列进行排序，然后将排序好的子序列合并成一个有序序列。

代码实现 (Java)

public class MergeSort {
    public static void mergeSort(int[] arr, int l, int r) {
        if (l < r) {
            int m = l + (r - l) / 2;

            mergeSort(arr, l, m);
            mergeSort(arr, m + 1, r);

            merge(arr, l, m, r);
        }
    }

    public static void merge(int[] arr, int l, int m, int r) {
        int n1 = m - l + 1;
        int n2 = r - m;

        int[] L = new int[n1];
        int[] R = new int[n2];

        for (int i = 0; i < n1; ++i)
            L[i] = arr[l + i];
        for (int j = 0; j < n2; ++j)
            R[j] = arr[m + 1 + j];

        int i = 0, j = 0, k = l;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }

        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        mergeSort(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) 空间，因此在空间受限的场景下需要谨慎使用。此外，在多线程环境下，归并排序可以并行执行，进一步提升排序效率。

快速排序 (Quick Sort)

原理

快速排序也是一种基于分治思想的排序算法。它的基本思想是：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。

代码实现 (Java)

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

                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[] 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)。最坏情况发生在每次选择的 pivot 都是最大或最小值时。为了避免最坏情况的发生，可以采用随机选择 pivot 的方式。快速排序是一种原地排序算法，不需要额外的空间，但由于递归调用，会占用一定的栈空间。在深度递归的情况下，可能会导致栈溢出。对于大规模数据，可以考虑使用迭代版本的快速排序。

堆排序 (Heap Sort)

原理

堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

代码实现 (Java)

public class HeapSort {
    public static void heapSort(int[] arr) {
        int n = arr.length;

        // 构建最大堆
        for (int i = n / 2 - 1; i >= 0; i--)
            heapify(arr, n, i);

        // 从堆中依次取出元素
        for (int i = n - 1; i > 0; i--) {
            // 将当前根节点（最大元素）与末尾元素交换
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // 重新构建堆
            heapify(arr, i, 0);
        }
    }

    // 堆化函数
    public static void heapify(int[] arr, int n, int i) {
        int largest = i; // 初始化最大值为根节点
        int l = 2 * i + 1; // 左子节点
        int r = 2 * i + 2; // 右子节点

        // 如果左子节点大于根节点
        if (l < n && arr[l] > arr[largest])
            largest = l;

        // 如果右子节点大于根节点
        if (r < n && arr[r] > arr[largest])
            largest = r;

        // 如果最大值不是根节点
        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            // 递归堆化子树
            heapify(arr, n, largest);
        }
    }

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

避坑经验

堆排序的时间复杂度为 O(n log n)，是一种不稳定的排序算法。堆排序不需要额外的空间，是一种原地排序算法。堆排序在实际应用中，常用于优先队列的实现。在构建堆的过程中，需要进行大量的比较和交换操作，因此性能可能不如快速排序。

掌握这七大排序算法的基本原理和应用场景，能够帮助我们更好地进行后端架构设计和性能优化。在实际开发中，要根据数据规模、数据特点以及性能要求，选择合适的排序算法。例如，对于小规模数据，可以选择插入排序或者选择排序；对于大规模数据，可以选择归并排序或者快速排序。同时，也要注意避免使用不合适的排序算法，导致系统性能下降。