4302 字
22 分钟
排序算法详解与实战
2026-01-21
技术
算法
/
排序
/
OI
/
算法竞赛

排序算法详解与实战#

排序算法是计算机科学中最基础也是最重要的算法之一，在OI竞赛中更是频繁出现。本文将系统讲解各种经典排序算法，从基础的O(n²)算法到高效的O(n log n)算法，并结合实际竞赛题目进行深入分析。

一、排序算法概述#

1.1 什么是排序#

排序是将一组数据按照特定顺序（通常是升序或降序）重新排列的过程。排序算法的效率直接影响程序的整体性能，因此在算法竞赛中选择合适的排序算法至关重要。

1.2 排序算法的分类#

按时间复杂度分类：

  • O(n²) 算法：冒泡排序、选择排序、插入排序
  • O(n log n) 算法：归并排序、快速排序、堆排序
  • O(n) 算法：计数排序、桶排序、基数排序（特定条件下）

按稳定性分类：

  • 稳定排序：相等元素的相对位置不变（冒泡、插入、归并）
  • 不稳定排序：相等元素的相对位置可能改变（选择、快速、堆排序）

1.3 评价标准#

  • 时间复杂度：算法执行的基本操作次数
  • 空间复杂度：额外占用的内存空间
  • 稳定性：相等元素是否保持原有顺序
  • 适用场景：数据规模、数据特征等

二、冒泡排序（Bubble Sort）#

2.1 算法原理#

冒泡排序是最简单直观的排序算法。它重复地遍历待排序数列，每次比较相邻两个元素，如果顺序错误就交换它们。这个过程会让较大的元素像气泡一样”浮”到数列的末端。

核心思想：

  1. 从数组开头开始，比较相邻的元素
  2. 如果前一个比后一个大，就交换它们
  3. 继续向后遍历，直到最后一对元素
  4. 此时最大的元素已经”冒泡”到了最后
  5. 重复以上步骤，每次减少一个待比较的元素

2.2 代码实现#

#include <iostream>
#include <vector>
using namespace std;


void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;  // 优化：检测是否发生交换
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        // 如果本轮没有发生交换，说明已经有序
        if (!swapped) break;
    }
}


int main() {
    vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
    bubbleSort(arr);


    cout << "排序后: ";
    for (int num : arr) {
        cout << num << " ";
    }
    return 0;
}

2.3 复杂度分析#

  • 时间复杂度：
    • 最好情况：O(n)（数组已经有序，只需一轮遍历）
    • 平均情况：O(n²)
    • 最坏情况：O(n²)（逆序排列）
  • 空间复杂度：O(1)（只需要常数级别的额外空间）
  • 稳定性：稳定（相等元素不会交换位置）

2.4 适用场景#

  • 数据规模较小（n < 100）
  • 数据基本有序
  • 教学演示

三、选择排序（Selection Sort）#

3.1 算法原理#

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

工作流程：

  1. 在未排序序列中找到最小元素
  2. 将其与未排序序列的第一个元素交换
  3. 将已排序序列的边界向后移动一位
  4. 重复步骤1-3，直到所有元素排序完成

3.2 代码实现#

void selectionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        // 在未排序部分找到最小元素
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        // 将找到的最小元素与第i个元素交换
        if (minIdx != i) {
            swap(arr[i], arr[minIdx]);
        }
    }
}

3.3 复杂度分析#

  • 时间复杂度：
    • 最好、平均、最坏情况都是 O(n²)
    • 比较次数固定：n(n-1)/2
  • 空间复杂度：O(1)
  • 稳定性：不稳定（交换操作可能改变相等元素的相对位置）

3.4 特点#

  • 交换次数最少：最多进行 n-1 次交换
  • 性能与数据初始状态无关
  • 实现简单但效率较低

四、插入排序（Insertion Sort）#

4.1 算法原理#

插入排序类似于整理扑克牌。将数组分为已排序和未排序两部分，每次从未排序部分取出一个元素，插入到已排序部分的正确位置。

核心步骤：

  1. 从第二个元素开始，认为第一个元素已经排好序
  2. 取出当前元素，在已排序序列中从后向前扫描
  3. 如果已排序元素大于当前元素，将该元素后移
  4. 重复步骤3，直到找到小于等于当前元素的位置
  5. 将当前元素插入到该位置

4.2 代码实现#

void insertionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;


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


// 优化版本：二分查找插入位置
void insertionSortBinary(vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        // 使用二分查找找到插入位置
        int left = 0, right = i - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] > key) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }


        // 移动元素并插入
        for (int j = i - 1; j >= left; j--) {
            arr[j + 1] = arr[j];
        }
        arr[left] = key;
    }
}

4.3 复杂度分析#

  • 时间复杂度：
    • 最好情况：O(n)（数组已排序）
    • 平均情况：O(n²)
    • 最坏情况：O(n²)（逆序排列）
  • 空间复杂度：O(1)
  • 稳定性：稳定

4.4 适用场景#

  • 小规模数据（n < 50）
  • 数据基本有序
  • 在线排序（数据逐个到达时）

五、归并排序（Merge Sort）#

5.1 算法原理#

归并排序采用分治思想，将数组递归地分成两半，分别排序后再合并。这是一种稳定且高效的排序算法。

分治步骤：

  1. 分解：将数组从中间分成两个子数组
  2. 递归：对两个子数组分别进行归并排序
  3. 合并：将两个有序子数组合并成一个有序数组

5.2 代码实现#

void merge(vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;


    // 创建临时数组
    vector<int> L(n1), R(n2);


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


    // 合并两个有序数组
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k++] = L[i++];
        } else {
            arr[k++] = R[j++];
        }
    }


    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}


void mergeSort(vector<int>& arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;


        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

5.3 复杂度分析#

  • 时间复杂度：O(n log n)（所有情况）
  • 空间复杂度：O(n)（需要额外的数组空间）
  • 稳定性：稳定

5.4 逆序对问题#

归并排序的一个重要应用是求解逆序对数量。逆序对指数组中满足 i < j 但 arr[i] > arr[j] 的元素对。

long long mergeAndCount(vector<int>& arr, int left, int mid, int right) {
    vector<int> L(arr.begin() + left, arr.begin() + mid + 1);
    vector<int> R(arr.begin() + mid + 1, arr.begin() + right + 1);


    long long count = 0;
    int i = 0, j = 0, k = left;
    int n1 = L.size(), n2 = R.size();


    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k++] = L[i++];
        } else {
            arr[k++] = R[j++];
            count += (n1 - i);  // 关键：计算逆序对
        }
    }


    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];


    return count;
}


long long mergeSortAndCount(vector<int>& arr, int left, int right) {
    long long count = 0;
    if (left < right) {
        int mid = left + (right - left) / 2;
        count += mergeSortAndCount(arr, left, mid);
        count += mergeSortAndCount(arr, mid + 1, right);
        count += mergeAndCount(arr, left, mid, right);
    }
    return count;
}

六、快速排序（Quick Sort）#

6.1 算法原理#

快速排序是最常用的排序算法之一，也采用分治思想。选择一个基准元素，将数组分为小于基准和大于基准的两部分，然后递归排序。

核心步骤：

  1. 选择基准元素（pivot）
  2. 分区操作：将小于基准的元素移到左边，大于基准的移到右边
  3. 递归地对左右两个分区进行快速排序

6.2 代码实现#

// 标准分区方法
int partition(vector<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++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}


void quickSort(vector<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);
    }
}


// 三路快排（处理大量重复元素）
void quickSort3Way(vector<int>& arr, int low, int high) {
    if (low >= high) return;


    int lt = low, gt = high;
    int pivot = arr[low];
    int i = low + 1;


    while (i <= gt) {
        if (arr[i] < pivot) {
            swap(arr[lt++], arr[i++]);
        } else if (arr[i] > pivot) {
            swap(arr[i], arr[gt--]);
        } else {
            i++;
        }
    }


    quickSort3Way(arr, low, lt - 1);
    quickSort3Way(arr, gt + 1, high);
}

6.3 优化技巧#

1. 随机化基准选择

int randomPartition(vector<int>& arr, int low, int high) {
    int randomIndex = low + rand() % (high - low + 1);
    swap(arr[randomIndex], arr[high]);
    return partition(arr, low, high);
}

2. 三数取中法

int medianOfThree(vector<int>& arr, int low, int high) {
    int mid = low + (high - low) / 2;
    if (arr[low] > arr[mid]) swap(arr[low], arr[mid]);
    if (arr[low] > arr[high]) swap(arr[low], arr[high]);
    if (arr[mid] > arr[high]) swap(arr[mid], arr[high]);
    swap(arr[mid], arr[high]);
    return partition(arr, low, high);
}

3. 小数组使用插入排序

void quickSortOptimized(vector<int>& arr, int low, int high) {
    if (high - low < 10) {  // 小数组直接使用插入排序
        insertionSort(arr);
        return;
    }
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSortOptimized(arr, low, pi - 1);
        quickSortOptimized(arr, pi + 1, high);
    }
}

6.4 复杂度分析#

  • 时间复杂度：
    • 最好情况：O(n log n)（每次都平分）
    • 平均情况：O(n log n)
    • 最坏情况：O(n²)（数组已排序或逆序）
  • 空间复杂度：O(log n)（递归栈空间）
  • 稳定性：不稳定

七、堆排序（Heap Sort）#

7.1 算法原理#

堆排序利用堆这种数据结构。堆是一个完全二叉树，分为最大堆和最小堆。堆排序通过构建最大堆，不断将堆顶元素（最大值）与末尾元素交换，然后调整堆。

核心步骤：

  1. 构建最大堆（从最后一个非叶子节点开始向下调整）
  2. 将堆顶元素与末尾元素交换
  3. 减小堆的大小，对新的堆顶进行向下调整
  4. 重复步骤2-3，直到堆大小为1

7.2 代码实现#

void heapify(vector<int>& arr, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;


    if (left < n && arr[left] > arr[largest])
        largest = left;


    if (right < n && arr[right] > arr[largest])
        largest = right;


    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}


void heapSort(vector<int>& arr) {
    int n = arr.size();


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


    // 依次取出堆顶元素
    for (int i = n - 1; i > 0; i--) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

7.3 复杂度分析#

  • 时间复杂度：O(n log n)（所有情况）
  • 空间复杂度：O(1)
  • 稳定性：不稳定

7.4 优势#

  • 时间复杂度稳定
  • 原地排序，空间效率高
  • 适合内存受限的场景

八、计数排序和桶排序#

8.1 计数排序（Counting Sort）#

适用于整数且范围不大的情况。

void countingSort(vector<int>& arr) {
    if (arr.empty()) return;


    int maxVal = *max_element(arr.begin(), arr.end());
    int minVal = *min_element(arr.begin(), arr.end());
    int range = maxVal - minVal + 1;


    vector<int> count(range, 0);
    vector<int> output(arr.size());


    // 统计每个元素出现次数
    for (int num : arr)
        count[num - minVal]++;


    // 计算累积计数
    for (int i = 1; i < range; i++)
        count[i] += count[i - 1];


    // 构建输出数组
    for (int i = arr.size() - 1; i >= 0; i--) {
        output[count[arr[i] - minVal] - 1] = arr[i];
        count[arr[i] - minVal]--;
    }


    arr = output;
}

复杂度： 时间O(n+k)，空间O(k)，其中k是数据范围

8.2 桶排序（Bucket Sort）#

void bucketSort(vector<float>& arr) {
    int n = arr.size();
    vector<vector<float>> buckets(n);


    // 将元素分配到桶中
    for (float num : arr) {
        int bucketIndex = n * num;
        buckets[bucketIndex].push_back(num);
    }


    // 对每个桶排序
    for (auto& bucket : buckets) {
        sort(bucket.begin(), bucket.end());
    }


    // 合并桶
    int index = 0;
    for (auto& bucket : buckets) {
        for (float num : bucket) {
            arr[index++] = num;
        }
    }
}

九、STL sort函数及自定义比较#

9.1 基本使用#

C++ STL提供的sort函数基于快速排序、堆排序和插入排序的混合算法（Introsort）。

#include <algorithm>
#include <vector>
using namespace std;


int main() {
    vector<int> arr = {5, 2, 8, 1, 9};


    // 升序排序
    sort(arr.begin(), arr.end());


    // 降序排序
    sort(arr.begin(), arr.end(), greater<int>());


    return 0;
}

9.2 自定义比较函数#

方法1：使用函数

bool compare(int a, int b) {
    return a > b;  // 降序
}
sort(arr.begin(), arr.end(), compare);

方法2：使用Lambda表达式

sort(arr.begin(), arr.end(), [](int a, int b) {
    return a % 10 < b % 10;  // 按个位数排序
});

方法3：结构体排序

struct Student {
    string name;
    int score;


    bool operator<(const Student& other) const {
        if (score != other.score)
            return score > other.score;  // 分数降序
        return name < other.name;        // 姓名升序
    }
};


vector<Student> students;
sort(students.begin(), students.end());

9.3 稳定排序#

stable_sort(arr.begin(), arr.end());  // 保持相等元素的相对顺序

十、典型OI题目与解法#

10.1 逆序对问题#

题目描述： 给定一个数组，求逆序对的数量。

洛谷P1908 逆序对

#include <iostream>
#include <vector>
using namespace std;


long long mergeAndCount(vector<int>& arr, int left, int mid, int right) {
    vector<int> temp(right - left + 1);
    int i = left, j = mid + 1, k = 0;
    long long count = 0;


    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
            count += (mid - i + 1);
        }
    }


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


    for (int p = 0; p < k; p++)
        arr[left + p] = temp[p];


    return count;
}


long long countInversions(vector<int>& arr, int left, int right) {
    long long count = 0;
    if (left < right) {
        int mid = left + (right - left) / 2;
        count += countInversions(arr, left, mid);
        count += countInversions(arr, mid + 1, right);
        count += mergeAndCount(arr, left, mid, right);
    }
    return count;
}


int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++)
        cin >> arr[i];


    cout << countInversions(arr, 0, n - 1) << endl;
    return 0;
}

10.2 第K大元素#

题目描述： 在未排序的数组中找到第k大的元素。

解法：快速选择算法

int partition(vector<int>& nums, int left, int right) {
    int pivot = nums[right];
    int i = left;
    for (int j = left; j < right; j++) {
        if (nums[j] >= pivot) {
            swap(nums[i], nums[j]);
            i++;
        }
    }
    swap(nums[i], nums[right]);
    return i;
}


int quickSelect(vector<int>& nums, int left, int right, int k) {
    if (left == right) return nums[left];


    int pivotIndex = partition(nums, left, right);


    if (k == pivotIndex) {
        return nums[k];
    } else if (k < pivotIndex) {
        return quickSelect(nums, left, pivotIndex - 1, k);
    } else {
        return quickSelect(nums, pivotIndex + 1, right, k);
    }
}


int findKthLargest(vector<int>& nums, int k) {
    return quickSelect(nums, 0, nums.size() - 1, k - 1);
}

10.3 合并K个有序数组#

题目描述： 合并k个已排序的数组。

解法：使用优先队列（堆）

#include <queue>


struct Element {
    int value;
    int arrayIdx;
    int elementIdx;


    bool operator>(const Element& other) const {
        return value > other.value;
    }
};


vector<int> mergeKArrays(vector<vector<int>>& arrays) {
    priority_queue<Element, vector<Element>, greater<Element>> pq;
    vector<int> result;


    // 将每个数组的第一个元素加入堆
    for (int i = 0; i < arrays.size(); i++) {
        if (!arrays[i].empty()) {
            pq.push({arrays[i][0], i, 0});
        }
    }


    while (!pq.empty()) {
        Element curr = pq.top();
        pq.pop();
        result.push_back(curr.value);


        // 如果当前数组还有元素，加入下一个元素
        if (curr.elementIdx + 1 < arrays[curr.arrayIdx].size()) {
            pq.push({
                arrays[curr.arrayIdx][curr.elementIdx + 1],
                curr.arrayIdx,
                curr.elementIdx + 1
            });
        }
    }


    return result;
}

10.4 区间合并#

题目描述： 给定若干区间，合并所有重叠的区间。

struct Interval {
    int start, end;
    bool operator<(const Interval& other) const {
        return start < other.start;
    }
};


vector<Interval> mergeIntervals(vector<Interval>& intervals) {
    if (intervals.empty()) return {};


    sort(intervals.begin(), intervals.end());
    vector<Interval> result;
    result.push_back(intervals[0]);


    for (int i = 1; i < intervals.size(); i++) {
        if (intervals[i].start <= result.back().end) {
            result.back().end = max(result.back().end, intervals[i].end);
        } else {
            result.push_back(intervals[i]);
        }
    }


    return result;
}

十一、总结与选择建议#

11.1 算法选择指南#

场景推荐算法原因
通用排序STL sort高效、稳定、久经考验
小数据量(n<50)插入排序简单高效
需要稳定排序归并排序/stable_sort保持相等元素顺序
空间受限堆排序O(1)空间复杂度
整数范围小计数排序O(n)时间复杂度
求逆序对归并排序同时完成排序和计数
求第K大快速选择O(n)平均时间

11.2 竞赛技巧#

  1. 优先使用STL sort：除非有特殊需求，STL的sort已经足够优秀
  2. 注意数据范围：大数据量避免O(n²)算法
  3. 考虑稳定性：某些题目要求保持相对顺序
  4. 自定义比较：灵活使用Lambda表达式
  5. 特殊优化：
    • 数据基本有序 → 插入排序
    • 大量重复元素 → 三路快排
    • 只需部分排序 → partial_sort

11.3 实战建议#

  • 熟练掌握：归并排序、快速排序、STL sort
  • 理解原理：每种算法的时间/空间复杂度
  • 灵活应用：根据题目特点选择合适的算法
  • 代码模板：准备好常用排序算法的模板
  • 调试技巧：使用小数据量测试，验证边界情况

参考资源#

  1. 《算法导论》- 排序算法经典教材
  2. 《算法竞赛进阶指南》- OI实战技巧
  3. 洛谷题库 - 排序专题练习
  4. Codeforces - 国际竞赛平台

练习建议：

  • 洛谷P1177: 【模板】快速排序
  • 洛谷P1908: 逆序对
  • LeetCode 215: 数组中的第K个最大元素
  • LeetCode 56: 合并区间
  • LeetCode 148: 排序链表

通过本文的学习，相信你已经对各种排序算法有了全面的理解。在OI竞赛中，排序是许多高级算法的基础，务必熟练掌握！

排序算法详解与实战
https://myblog-590.pages.dev/posts/algorithm-sorting/
作者
谢星宇
发布于
2026-01-21
许可协议
CC BY-NC-SA 4.0

相关文章

1

网络流与二分图匹配：从CSP-S到IOI

网络流算法完整教程，涵盖最大流、最小费用流、二分图匹配等核心内容

技术 2026年1月21日
2

博弈论算法详解：从CSP-S到IOI

博弈论完整教程，涵盖Nim游戏、SG函数、各类经典博弈问题

技术 2026年1月21日
3

数论算法详解：从CSP-S到IOI

数论算法完整教程，涵盖质数、GCD、快速幂、逆元、欧拉函数等核心内容

技术 2026年1月21日
高级数据结构详解：从CSP-S到IOI
图论算法详解
© 2026 谢星宇. All Rights Reserved. / RSS / Sitemap
Powered by Astro & Fuwari