C++ 常见排序实现及性能比较

C++ 作为一种极具表达力的编程语言，不仅在传统的系统编程中表现优异，还在数据处理领域展现了强大的能力。无论是处理大规模数据还是小规模数据，C++ 提供了多种高效排序算法。以下将分别实现并讨论常见的排序算法，包括归并排序、冒泡排序、STL快速排序、选择排序、快速排序、插入排序以及堆排序。

1. 归并排序 (MergeSort)

归并排序是一种经典的 comparatorSort 排序算法，其工作原理是将数组分成两半，分别对每个半部分进行排序，然后再将有序的两半合并成一个完整的有序数组。归并排序的时间复杂度是 O(n log n)，在处理大数据量时表现优异。

void test_MergeSort(std::vector
   
     &array) {    int len = array.size();    MergeSort(array, 0, len - 1);    // 预定义的排序结果数组    std::vector
    
      result;    result = MergeSort(array, 0, len - 1);    // 打印测试结果    std::cout << "MergeSort : ";    for (int i = 0; i < len; ++i) {        std::cout << result[i] << " ";    }    std::cout << std::endl;}

归并排序的实现关键在于 MergeSort 和 Merge 函数。MergeSort Function recursively sorts the array by dividing it into left and right halves, sorting each half, and then merging them. Merge函数负责合并两个有序数组。

2. 冒泡排序 (BubbleSort)

冒泡排序是一种最简单的排序算法，通过多次视交换相邻元素，逐渐将较大的元素“冒”到位。在 données大小为 n 的情况下，其所需时间复杂度介于 O(n^2) 和 O(n^2) 之间。虽然冒泡排序的时间复杂度较高，但其实现逻辑简单，被用作基础排序算法理解。

void test_BubbleSort(std::vector
   
     &array) {    int len = array.size();    BubbleSort(array);    std::cout << "BubbleSort : ";    for (int i = 0; i < len; ++i) {        std::cout << array[i] << " ";    }    std::cout << std::endl;}

冒泡排序的实现代码简单明了，通过循环$n-1$次，每次循环中将最大的元素“冒”到当前位置，并逐步构建有序数组。

3. STL 快速排序 (StlSort)

STL 提供了内置的快速排序实现，直接使用 std::sort 函数即可完成排序。在 C++ 标准库中，std::sort 使用快速排序算法，其效率在一般情况下非常高，时间复杂度为 O(n log n)。

#include 
   
    void test_StlSort(std::vector
    
      array) {    int len = array.size();    std::sort(array.begin(), array.end());    std::cout << "StlSort : ";    for (int i = 0; i < len; ++i) {        std::cout << array[i] << " ";    }    std::cout << std::endl;}

4. 选择排序 (SelectionSort)

选择排序的工作原理是每次从当前未排序的元素中选择最小的元素放到前面，直到所有元素已排序。其时间复杂度为 O(n^2)，通常用于小数据量的排序。

void test_SelectionSort(std::vector
   
     &array) {    int len = array.size();    SelectionSort(array);    std::cout << "SelectionSort : ";    for (int i = 0; i < len; ++i) {        std::cout << array[i] << " ";    }    std::cout << std::endl;}

5. 快速排序 (QuickSort)

快速排序是一种高效的分区排序算法，因为其时间复杂度平均为 O(n log n)，早期版本的性能可能不如当前。其基本思想是选择一个 pivot 元素，将比 pivot 小的元素放在左边，比 pivot 大的放在右边，递归地对左右子数组进行排序。

void test_QuickSort(std::vector
   
     &array) {    int len = array.size();    QuickSort(array, 0, len - 1);    std::cout << "QuickSort : ";    for (int i = 0; i < len; ++i) {        std::cout << array[i] << " ";    }    std::cout << std::endl;}

6. 插入排序 (InsertSort)

插入排序通过从后往前构建有序数组，逐步将当前元素插入到正确位置。其时间复杂度为 O(n^2)，在数据量小的情况下表现较好。

void test_InsertSort(std::vector
   
     &array) {    int len = array.size();    InsertSort(array);    std::cout << "InsertSort : ";    for (int i = 0; i < len; ++i) {        std::cout << array[i] << " ";    }    std::cout << std::endl;}

7. 堆排序 (HeapSort)

堆排序是基于堆数据结构的排序方法，其核心操作是 adjust 和 siftDown。首先构建一个大根堆，然后通过 siftDown 操作将最大元素移动到数组最终位置，递归地排序数组。

void test_HeapSort(std::vector
   
     &array) {    int len = array.size();    HeapSort(array);    std::cout << "HeapSort : ";    for (int i = 0; i < len; ++i) {        std::cout << array[i] << " ";    }    std::cout << std::endl;}

测试结果分析

所有排序算法都在同一数据集 [3, 5, 9, 1, 7, 6, 8, 2, 0, 4] 上进行测试。正如上述代码所示，所有排序算法在排序完成后都输出了同样的排序结果 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]。看似所有排序都成功了，但实际上这只是测试代码的一个示例，实际应用中每个排序算法的性能表现可能有很大不同。

需要注意的是，测试结果仅为排序是否正确的验证，并不反映每种排序算法的性能优劣。在真正的应用中，应该根据具体需求选择最优的排序算法，例如归并排序或快速排序。

上一篇：Clion中github工具的配置

下一篇：关于C++重载、重写、重定义的理解

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！