C++原地排序算法详解（零基础掌握高效排序技巧）

1. 冒泡排序（Bubble Sort）

冒泡排序是最简单的原地排序算法之一。它通过重复遍历数组，比较相邻元素并交换位置，使得较大的元素像“气泡”一样逐渐“浮”到数组末尾。

算法步骤：

• 从第一个元素开始，依次比较相邻两个元素；
• 如果前一个比后一个大，则交换它们；
• 重复上述过程，直到没有需要交换的元素为止。

C++代码实现：

#include <iostream>#include <vector>void bubbleSort(std::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]) {                std::swap(arr[j], arr[j + 1]);                swapped = true;            }        }        // 如果某一轮没有发生交换，说明已经有序        if (!swapped) break;    }}int main() {    std::vector<int> nums = {64, 34, 25, 12, 22, 11, 90};    bubbleSort(nums);    for (int num : nums) {        std::cout << num << " ";    }    return 0;}

冒泡排序的时间复杂度为 O(n²)，虽然效率不高，但逻辑清晰，非常适合初学者理解排序的基本思想。

2. 快速排序（Quick Sort）

快速排序是实践中最常用的快速排序C++实现之一，它采用“分治法”策略，平均时间复杂度为 O(n log n)，且是典型的原地排序算法。

算法步骤：

• 选择一个“基准”（pivot）元素；
• 将数组划分为两部分：小于基准的放左边，大于基准的放右边；
• 递归地对左右两部分进行快速排序。

C++代码实现：

#include <iostream>#include <vector>int partition(std::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;            std::swap(arr[i], arr[j]);        }    }    std::swap(arr[i + 1], arr[high]);    return i + 1;}void quickSort(std::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); // 排序右半部分    }}int main() {    std::vector<int> nums = {10, 7, 8, 9, 1, 5};    quickSort(nums, 0, nums.size() - 1);    for (int num : nums) {        std::cout << num << " ";    }    return 0;}

快速排序虽然最坏情况时间复杂度为 O(n²)，但在大多数实际场景中表现优异，是 C++ 标准库 std::sort 的底层实现之一。

总结

通过本教程，你已经掌握了两种经典的C++原地排序方法：简单直观的冒泡排序和高效实用的快速排序。无论你是面试准备还是项目开发，理解这些基础算法都将为你打下坚实的基础。

记住，原地排序的核心在于不使用额外数组，只用少量变量完成排序。希望你能动手实践上面的代码，加深理解！

关键词回顾：C++原地排序、原地排序算法、快速排序C++、冒泡排序C++。