c++排序算法

#include <iostream>
#include <vector>
#include <algorithm>

// 快速排序示例
void quickSort(std::vector<int>& arr, int left, int right) {
    if (left >= right) return;

    int pivot = arr[left];
    int i = left, j = right;

    while (i < j) {
        while (i < j && arr[j] >= pivot) --j;
        arr[i] = arr[j];
        while (i < j && arr[i] <= pivot) ++i;
        arr[j] = arr[i];
    }
    arr[i] = pivot;

    quickSort(arr, left, i - 1);
    quickSort(arr, i + 1, right);
}

int main() {
    std::vector<int> arr = {3, 6, 8, 10, 1, 2, 1};

    // 使用STL自带的sort函数进行排序
    std::sort(arr.begin(), arr.end());
    std::cout << "Sorted array using STL sort: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 使用自定义的快速排序算法
    std::vector<int> arr2 = {3, 6, 8, 10, 1, 2, 1};
    quickSort(arr2, 0, arr2.size() - 1);
    std::cout << "Sorted array using quick sort: ";
    for (int num : arr2) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

解释说明

1. STL std::sort:

   • C++ 标准库提供了非常高效的排序算法 std::sort，它是一个模板函数，可以对任意类型的容器进行排序。
   • 在代码中，我们使用 std::sort 对一个整数向量进行了排序，并输出排序后的结果。

2. 自定义快速排序 (quickSort):

   • 快速排序是一种分治算法，通过选择一个基准元素（pivot），将数组分为两部分：一部分小于基准元素，另一部分大于基准元素，然后递归地对这两部分进行排序。
   • 在代码中，我们实现了一个简单的快速排序算法，并对其进行了测试。

3. 主函数 (main):

   • 主函数中首先使用了 std::sort 进行排序，然后使用自定义的快速排序算法进行排序，并分别输出结果。