怎样用指针实现C++数组排序手写快速排序算法示例-C++-PHP中文网

怎样用指针实现C++数组排序手写快速排序算法示例

P粉602998670

发布： 2025-07-31 11:05:01

原创

546人浏览过

快速排序是一种分而治之的排序算法，通过选择基准值将数组分为两部分并递归排序。1. 定义排序函数，参数为两个int*指针表示数组范围；2. 选择基准值，通常取最左边元素；3. 使用双指针从左右扫描并交换不符合顺序的元素；4. 将基准值放到正确位置后递归处理左右子数组；5. 注意指针边界、基准选择及指针运算避免越界。

怎样用指针实现C++数组排序手写快速排序算法示例

在 C++ 中，使用指针操作数组并实现排序算法是一种常见的做法，尤其是当你想深入理解底层数据操作和内存管理时。快速排序（Quick Sort）作为经典的分治排序算法，非常适合用指针来实现。

什么是快速排序？

快速排序的核心思想是“分而治之”。它选择一个基准值（pivot），将数组分成两部分：一部分比 pivot 小，另一部分比 pivot 大，然后递归地对这两部分继续排序。

使用指针的好处在于，我们不需要额外拷贝数组，而是通过移动指针来访问和操作数组元素，效率更高。

立即学习“C++免费学习笔记（深入）”；

如何用指针实现快速排序？

要用手写的方式实现快排，关键在于如何用指针来表示数组的起始和结束位置，并在递归过程中正确传递这些信息。

步骤如下：

定义排序函数，参数为两个 int* 指针，分别指向数组的起始和末尾。
找到基准值，通常选中间或第一个元素。
使用双指针从左右两端扫描，交换不符合顺序的元素。
递归处理左右子数组。

快速排序代码示例（使用指针）

下面是一个简单的实现：

简篇AI排版

AI排版工具，上传图文素材，秒出专业效果！

554

查看详情

#include <iostream>
using namespace std;

void quickSort(int* left, int* right) {
    // 如果只有一个元素或者没有元素，直接返回
    if (left >= right) return;

    int pivot = *left;  // 以最左边的数为基准
    int* i = left;
    int* j = right;

    while (i < j) {
        // 从右往左找比 pivot 小的
        while (i < j && *j >= pivot) j--;
        // 从左往右找比 pivot 大的
        while (i < j && *i <= pivot) i++;

        if (i < j) swap(*i, *j);
    }

    swap(*left, *i);  // 把 pivot 放到中间位置

    // 递归左右两边
    quickSort(left, i - 1);
    quickSort(i + 1, right);
}

int main() {
    int arr[] = {5, 3, 8, 4, 2};
    int n = sizeof(arr) / sizeof(arr[0]);

    quickSort(arr, arr + n - 1);

    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";
    cout << endl;

    return 0;
}

登录后复制

常见问题与注意事项

指针边界判断很重要：一定要确保 left < right，否则会出现死循环或越界访问。
基准值的选择影响性能：可以随机选择 pivot 或者三数取中，避免极端情况（如数组已有序）。
swap 函数用的是标准库的：如果你不引入 <algorithm>，可以自己写一个简单的 swap：
```
void swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}
```
登录后复制
注意指针运算不要越界：比如 arr + n 是最后一个元素的下一个地址，不能直接解引用。