跳到主要内容 C/C++ 基础排序算法汇总 | 极客日志
C++ 算法
C/C++ 基础排序算法汇总 本文汇总了 C 语言和 C++ 中的基础排序算法。C 语言部分涵盖了冒泡、选择、插入、快速及归并排序的实现原理与代码示例，分析了时间与空间复杂度。C++ 部分介绍了标准库 algorithm 中的 std::sort 用法，包括默认升序、降序及自定义比较器；还涉及 C++20 Ranges 排序特性以及 list、set 等容器自带的排序功能。内容旨在帮助开发者掌握常见排序策略及其在不同语言环境下的应用。
C/C++ 基础排序算法汇总
C 语言排序算法实现
冒泡排序
冒泡排序依次对相邻两个元素的值进行比较，若发现前一个数大于后一个数则交换，使得较大的元素一步一步移动到数组的末尾。
void sort (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 ]) {
int temp = arr[j];
arr[j] = arr[j + 1 ];
arr[j + 1 ] = temp;
}
}
}
}
选择排序
选择排序每次从未排序部分选择最小（或最大）元素，放到已排序部分的末尾。
void selectionSort (int arr[], int n) for (int i = 0 ; i < n - 1 ; i++) {
int minIdx = i;
for (int j = i + 1 ; j < n; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
if (minIdx != i) {
int temp = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = temp;
}
}
}
微信扫一扫，关注极客日志 微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
相关免费在线工具 加密/解密文本 使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
Base64 字符串编码/解码 将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
Base64 文件转换器 将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
Markdown 转 HTML 将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
HTML 转 Markdown 将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
JSON 压缩 通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online
时间复杂度 ：O(n²)
空间复杂度 ：O(1)
插入排序 插入排序将数组分为已排序和未排序两部分，每轮遍历将未排序部分的第一个元素插入到已排序部分的正确位置。
void insertionSort (int arr[], int n) for (int i = 1 ; i < n; i++) {
int key = arr[i];
int j = i - 1 ;
while (j >= 0 && arr[j] > key) {
arr[j + 1 ] = arr[j];
j--;
}
arr[j + 1 ] = key;
}
}
快速排序 快速排序的核心思想是分治法。选择一个基准元素，将数组分成两个子数组（左子数组元素 ≤ pivot，右子数组元素 > pivot），然后递归地对两个子数组进行排序。
以中间元素为基准 void swap (int * a, int * b) int temp = *a;
*a = *b;
*b = temp;
}
void quickSort (int arr[], int left, int right) if (left >= right) return ;
int mid = left + (right - left) / 2 ;
int pivot = arr[mid];
int i = left;
int j = right;
while (i <= j) {
while (arr[j] > pivot && j >= left) j--;
while (arr[i] < pivot && i <= right) i++;
if (i <= j) {
swap (&arr[i], &arr[j]);
i++;
j--;
}
}
quickSort (arr, left, j);
quickSort (arr, i, right);
}
归并排序 归并排序是典型的分治算法。将数组递归地分成两半，直到每个子数组只有一个元素，然后将已排序的子数组合并成一个完整的有序数组。
#include <cstring>
#include <cstdlib>
void _MergeSort(int * arr, int left, int right, int * temp) {
if (left == right) return ;
int mid = (left + right) / 2 ;
_MergeSort(arr, left, mid, temp);
_MergeSort(arr, mid + 1 , right, temp);
int begin1 = left, end1 = mid;
int begin2 = mid + 1 , end2 = right;
int i = left;
while (begin1 <= end1 && begin2 <= end2) {
if (arr[begin1] < arr[begin2]) {
temp[i++] = arr[begin1++];
} else {
temp[i++] = arr[begin2++];
}
}
while (begin1 <= end1) temp[i++] = arr[begin1++];
while (begin2 <= end2) temp[i++] = arr[begin2++];
memcpy (arr + left, temp + left, sizeof (int ) * (right - left + 1 ));
}
void MergeSort (int * arr, int n) int * temp = (int *)malloc (sizeof (int ) * n);
_MergeSort(arr, 0 , n - 1 , temp);
free (temp);
}
C++ 标准库排序
中的排序函数
std::sort - 主要排序函数 #include <algorithm>
#include <vector>
#include <iostream>
int main () int > nums = {5 , 2 , 8 , 1 , 9 , 3 };
std::sort (nums.begin (), nums.end ());
std::sort (nums.begin (), nums.end (), std::greater <int >());
return 0 ;
}
std::sort (nums.begin (), nums.end (), [](int a, int b) {
return a > b;
});
C++20 Ranges 排序 #include <algorithm>
#include <vector>
#include <ranges>
int main () int > nums = {5 , 2 , 8 , 1 , 9 , 3 };
std::ranges::sort (nums);
struct Person {
std::string name;
int age;
};
std::vector<Person> people = {{"Alice" , 25 }, {"Bob" , 20 }};
std::ranges::sort (people, {}, &Person::age);
}
容器自带排序方法
std::list 和 std::forward_list #include <list>
std::list<int > lst = {5 , 2 , 8 , 1 , 9 , 3 };
lst.sort ();
lst.sort (std::greater <int >());
std::set 和 std::map（自动排序） #include <set>
#include <map>
std::set<int > s = {5 , 2 , 8 , 1 , 9 , 3 };
auto cmp = [](int a, int b) { return a > b; };
std::set<int , decltype (cmp) > descendingSet (cmp) ;
