十大排序算法

简介

对十大经典排序算法的简述，部分已给出示例代码（C++、Java），随缘更新。

选择排序

• 原理：每次从待排序区间中找到最小（或最大）元素，将其与区间首位元素交换，然后缩小待排序区间（排除已排序元素），重复直至完成。
• 核心：不断 “选择” 剩余元素中的最值并放到正确位置。

C++Java

vector<int> selectionSort(vector<int> arr) {
    for (int i = 0; i < arr.size(); i++) {
        int minIndex = i;
        for (int j = i + 1; j < arr.size(); j++) {
            if (arr[minIndex] > arr[j]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            swap(arr[i], arr[minIndex]);
        }
    }
    return arr;
}

冒泡排序

• 原理：通过相邻元素的两两比较和交换，使较大（或较小）的元素像 “气泡” 一样逐渐 “上浮” 到数组末端。优化版本可在某次遍历无交换时提前结束（说明已有序）。
• 核心：相邻元素比较交换，逐步将最值推到末端。

C++Java

插入排序

• 原理：将数组分为 “已排序” 和 “未排序” 两部分，每次从 “未排序” 部分取一个元素，插入到 “已排序” 部分的正确位置（通过与已排序元素比较后移位）。
• 核心：类似整理扑克牌，将新元素 “插入” 到已有序的序列中。

C++Java

希尔排序

• 原理：插入排序的优化版，通过 “步长” 将数组分为多个子序列，对每个子序列进行插入排序；逐步减小步长（最终为 1），最后一次步长为 1 时即普通插入排序。
• 核心：通过大步长先将数组 “粗略排序”，减少后续插入排序的移动次数。

C++Java

// 希尔排序函数
void shellSort (std::vector<int>& arr) {
    int n = arr.size ();

    // 初始步长为数组长度的一半，之后逐步减半
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // 对每个子序列进行插入排序
        for (int i = gap; i < n; i++) {
            int temp = arr[i];  // 保存当前待插入元素
            int j;

            // 移动同组中比 temp 大的元素，为 temp 找到合适位置
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;  // 插入元素
        }
    }
}

归并排序

• 原理：采用 “分治” 思想，将数组递归拆分为两个子数组，直至子数组长度为 1（天然有序）；然后将两个有序子数组合并为一个更大的有序数组，最终合并为完整有序数组。
• 核心：先 “分” 后 “合”，合并时利用两个子数组的有序性高效合并。

C++Java

快速排序

• 原理：分治思想的典型应用，选择一个 “基准元素”，将数组分为两部分：小于基准的元素放左侧，大于基准的放右侧（基准位置固定）；然后递归处理左右两部分。
• 核心：通过基准元素将数组 “分区”，减少问题规模。

C++Java

堆排序

• 原理：利用 “堆” 数据结构（完全二叉树）的特性，先将数组构建为大顶堆（或小顶堆），此时堆顶为最大值（或最小值）；将堆顶与末尾元素交换，缩小堆的范围并重新调整堆结构，重复直至排序完成。
• 核心：通过堆的调整快速获取最值并放到正确位置。

C++Java

计数排序

• 原理：非比较类排序，适用于整数数据。先统计每个元素出现的次数（用 “计数数组” 记录），然后根据计数数组的累积值，计算每个元素在结果数组中的位置，最后反向填充结果数组。
• 核心：通过 “计数” 直接确定元素位置，无需比较。

C++Java

桶排序

• 原理：将数据分到若干个 “桶” 中（每个桶对应一个范围），对每个桶内的元素单独排序（可选用其他排序算法），最后按桶的顺序合并所有桶的元素。
• 核心：利用数据分布特性，通过 “分桶” 减少每个桶内的排序规模。

C++Java

基数排序

• 原理：非比较类排序，按 “基数”（如数字的个位、十位、百位）从低到高（或从高到低）依次排序。每次按当前基数对所有元素分组，分组后按顺序拼接，重复直至所有基数处理完毕。
• 核心：按 “位” 分层排序，依赖低位排序结果为高位排序服务。

C++Java