C++ 补充之常用排序算法

C++ 补充之常���排序算法

常用的排序算法主要包括冒泡排序、选择排序、插入排序、快速排序、归并排序和堆排序，下面简单介绍一下它们的概念和原理：

1. 冒泡排序（Bubble Sort）：

   冒泡排序是一种基础的排序算法，它重复地走访要排序的元素列，依次比较相邻两个元素的大小，如果顺序不对则交换它们。通过多次遍历，每次最大的元素会慢慢“冒泡”到正确的位置。

2. 选择排序（Selection Sort）：

   选择排序是一种简单直观的排序算法，基本思路是每次在未排序的数据中选择最小（或最大）的元素，放到已排序部分的末尾。重复这个过程，直到所有元素都排序完毕。

3. 插入排序（Insertion Sort）：

   插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序类似于扑克牌整理手中的牌的过程。

4. 快速排序（Quick Sort）：

   快速排序是一种高效的排序算法，采用分治策略将数组分成两部分，然后递归地对子数组进行排序。具体做法是选择一个基准值，将小于基准值的元素放到左边，大于基准值的元素放到右边，最终实现整个数组的排序。

5. 归并排序（Merge Sort）：

   归并排序也是一种分治算法，将数组一分为二，分别对左右两部分进行排序，然后合并两个有序数组以获得最终有序结果。归并排序的关键在于合并操作。

6. 堆排序（Heap Sort）：

   堆排序利用堆这种数据结构来实现排序，堆是一个完全二叉树，可以分为最大堆和最小堆。堆排序首先将数组构建成一个最大堆或最小堆，然后不断取出堆顶元素（最大或最小值），再调整剩余元素使之重新满足堆的性质，最终得到有序序列。

每种排序算法都有其适用的场景和优缺点，根据具体情况选择合适的算法能够提高排序的效率。

C++ 补充之常用排序算法sort

C++标准库中的sort函数使用的是快速排序（Quick Sort）和插入排序（Insertion Sort）的混合算法，称为Introsort。具体原理如下：

1. 首先，sort函数会检测到排序的元素数量是否超过了阈值（通常是16个元素）。如果超过了阈值，将使用快速排序算法。

2. 快速排序通过选取一个基准元素（pivot），将待排序序列分为两部分：小于等于基准元素的部分和大于基准元素的部分。然后，分别对这两部分进行递归地快速排序。这样，最终整个序列就会有序。

3. 如果排序的元素数量较少（小于等于阈值），sort函数将转而使用插入排序算法。

4. 插入排序算法从第二个元素开始，将每一个元素插入到已排序好的部分中的正确位置，直到所有元素都被插入。这种算法能够在元素数量较少时表现出良好的性能。

下面以一个例子来说明sort函数的使用：

#include #include #include int main() {    std::vector nums = {5, 2, 8, 4, 1, 9};    // 使用sort函数对nums进行排序    std::sort(nums.begin(), nums.end());    // 输出排序后的结果    for (int num : nums) {        std::cout     std::vector1, 2, 3, 4, 5};    // 使用std::random_device和std::default_random_engine生成随机数种子    std::random_device rd;    std::default_random_engine rng(rd());    // 使用std::shuffle函数对nums进行随机重排    std::shuffle(nums.begin(), nums.end(), rng);    // 输出重排后的结果    for (int num : nums) {        std::cout     std::vector1, 3, 5, 7};    std::vector2, 4, 6, 8};    // 目标序列，用于存放合并后的有序序列    std::vector        std::cout     std::vector1, 2, 3, 4, 5};    // 使用std::reverse函数对nums进行逆序操作    std::reverse(nums.begin(), nums.end());    // 输出逆序后的结果    for (int num : nums) {        std::cout