legongju.com
我们一直在努力
2025-01-15 08:14 | 星期三

c++快排函数如何实现高效排序

C++中的快速排序(Quick Sort)是一种高效的排序算法,其基本思想是通过选取一个基准元素,将数组分为两部分,使得一部分的元素都小于基准元素,另一部分的元素都大于基准元素,然后对这两部分递归地进行快速排序。

以下是一个简单的C++快速排序实现:

#include
#include
using namespace std;

// 快速排序的分区函数
int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[low]; // 选取第一个元素作为基准
    while (low< high) {
        while (low< high && arr[high] >= pivot) {
            high--;
        }
        arr[low] = arr[high]; // 将比基准小的元素移到左边
        while (low< high && arr[low] <= pivot) {
            low++;
        }
        arr[high] = arr[low]; // 将比基准大的元素移到右边
    }
    arr[low] = pivot; // 把基准元素放到正确的位置
    return low; // 返回基准元素的索引
}

// 快速排序的递归函数
void quickSort(vector<int>& arr, int low, int high) {
    if (low< high) {
        int pivotIndex = partition(arr, low, high); // 获取基准元素的索引
        quickSort(arr, low, pivotIndex - 1); // 对左侧子数组进行快速排序
        quickSort(arr, pivotIndex + 1, high); // 对右侧子数组进行快速排序
    }
}

int main() {
    vector arr = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    quickSort(arr, 0, arr.size() - 1);
    for (int i = 0; i < arr.size(); i++) {
        cout<< arr[i] << " ";
    }
    cout<< endl;
    return 0;
}

这个实现中,partition函数用于将数组划分为两部分,quickSort函数则是递归地对这两部分进行排序。在main函数中,我们创建了一个包含一些整数的向量,并调用quickSort函数对其进行排序。最后,我们打印出排序后的结果。

未经允许不得转载 » 本文链接:https://www.legongju.com/article/108226.html

相关推荐

  • atoi在C++中的性能优化

    atoi在C++中的性能优化

    在C++中,可以通过以下几种方法来优化atoi函数的性能: 使用更高效的字符串转换方法:可以使用更高效的字符串转换方法,如使用stringstream、stoi或者自定义的字...

  • C++中atoi处理异常的方法

    C++中atoi处理异常的方法

    在C++中,可以使用try-catch语句来处理atoi函数可能引发的异常。具体的方法如下:
    #include #include int main() { const char* str = "123abc"; int resul...

  • 如何用C++实现atoi函数

    如何用C++实现atoi函数

    #include #include int myAtoi(std::string str) { int sign = 1, base = 0, i = 0; // skip leading whitespaces while (str[i] == ' ') { i++; } // check for...

  • C++里atoi转换字符串的技巧

    C++里atoi转换字符串的技巧

    在C++中,可以使用std::stoi函数来将字符串转换为整数。std::stoi函数接受一个字符串作为参数,并返回相应的整数值。例如:
    #include #include int main() ...

  • c++中coredump与异常处理的区别是什么

    c++中coredump与异常处理的区别是什么

    C++中的coredump和异常处理是两个不同的概念,它们之间有一些关联但也有明显的区别 Coredump:
    Coredump是操作系统在程序崩溃时生成的一种文件,用于记录程...

  • c++程序coredump时如何定位问题

    c++程序coredump时如何定位问题

    当C++程序产生coredump时,可以通过以下步骤定位问题: 确认coredump文件的生成:首先,需要确保操作系统允许生成coredump文件。在Linux系统中,可以使用ulimit ...

  • c++中如何避免coredump的发生

    c++中如何避免coredump的发生

    在C++中,避免core dump(核心转储)的发生可以通过以下方法来实现: 使用智能指针:C++11引入了智能指针,如std::shared_ptr和std::unique_ptr,它们可以自动管...

  • 如何分析c++程序的coredump文件

    如何分析c++程序的coredump文件

    分析 C++ 程序的 coredump 文件通常需要以下几个步骤: 获取 coredump 文件:当程序崩溃时,操作系统会生成一个包含程序运行时内存信息的文件。这个文件就是 cor...