解析C++排序算法

排序算法基础概念

1.1 排序的定义与分类

排序是将一组数据按照特定顺序重新排列的过程。根据排序方式可分为：

• 比较排序：通过比较元素决定顺序（如快速排序、归并排序）

• 非比较排序：不通过比较确定顺序（如计数排序、基数排序）

1.2 算法复杂度分析

• 时间复杂度：最好/最坏/平均情况

• 空间复杂度：原地排序与非原地排序

• 稳定性：相等元素相对位置是否改变

第二章 基础排序算法实现

2.1 冒泡排序

void bubbleSort(int arr[], int n) {for (int i = 0; i < n-1; i++)     for (int j = 0; j < n-i-1; j++)if (arr[j] > arr[j+1])swap(arr[j], arr[j+1]);
}

时间复杂度分析：O(n²)

2.2 选择排序

void selectionSort(int arr[], int n) {for (int i = 0; i < n-1; i++) {int min_idx = i;for (int j = i+1; j < n; j++)if (arr[j] < arr[min_idx])min_idx = j;swap(arr[min_idx], arr[i]);}
}

[... 此处省略约28000字内容，包含插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序的详细实现与分析，以及STL sort算法的源码解析、并行排序算法、排序算法优化技巧等章节...]

第十章 现代C++中的排序工具

10.1 STL排序算法比较

• std::sort：基于introsort的混合算法

• std::stable_sort：稳定排序保证

• std::partial_sort：部分排序

• std::nth_element：选择第n小元素

10.2 并行排序实现

#include <execution>
std::sort(std::execution::par, vec.begin(), vec.end());