c/c++蓝桥杯经典编程题100道（9）数组排序
数组排序
->返回c/c++蓝桥杯经典编程题100道-目录
目录
数组排序
一、题型解释
二、例题问题描述
三、C语言实现
解法1：冒泡排序（难度★）
解法2：选择排序（难度★）
解法3：快速排序（难度★★★）
四、C++实现
解法1：使用STL的sort函数（难度★☆）
解法2：自定义排序规则（难度★★）
解法3：归并排序（难度★★★）
五、总结对比表
一、题型解释
数组排序是将数组元素按特定顺序（升序、降序或自定义规则）重新排列的操作。常见题型：
-
基础排序：将数组按升序或降序排列（如
[3,1,4]→[1,3,4]）。 -
稳定排序：相同元素的相对顺序不变（如按姓名排序后，同分学生的顺序不变）。
-
条件排序：按自定义规则排序（如按绝对值、奇偶性等）。
-
部分排序：仅排序数组的一部分（如前k个元素）。
二、例题问题描述
例题1：输入数组 [5, 2, 9, 1, 5]，输出升序排列结果 [1, 2, 5, 5, 9]。
例题2：输入数组 [-3, 1, -5, 4]，按绝对值升序排列输出 [1, -3, 4, -5]。
例题3：输入数组 [7, 3, 8, 5]，输出降序排列结果 [8, 7, 5, 3]。
三、C语言实现
解法1：冒泡排序（难度★）
通俗解释：
-
像水中的气泡，每次将最大的元素“冒”到数组末尾。
c
#include <stdio.h>
void bubbleSort(int arr[], int n) {
// 外层循环：控制排序轮数（每一轮确定一个最大值的位置）
for (int i = 0; i < n-1; i++) {
// 内层循环：比较相邻元素并交换
for (int j = 0; j < n-1-i; j++) {
if (arr[j] > arr[j+1]) {
// 交换元素（大的往后“冒”）
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
int main() {
int arr[] = {5, 2, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, n);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]); // 输出 1 2 5 5 9
}
return 0;
}代码逻辑：
-
外层循环：共进行
n-1轮（每轮确定一个最大值的位置）。 -
内层循环：每轮比较相邻元素，若前大后小则交换。
-
优化：第
i轮时，末尾i个元素已有序，无需再比较。 -
时间复杂度：O(n²)（最坏情况）。
解法2：选择排序（难度★）
通俗解释：
-
每次从剩余元素中选最小的，放到已排序序列末尾。
c
#include <stdio.h>
void selectionSort(int arr[], int n) {
for (int i = 0; i < n-1; i++) {
int minIndex = i; // 假设当前元素是最小值
// 遍历剩余元素，找到实际最小值的位置
for (int j = i+1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j; // 更新最小值位置
}
}
// 将最小值与当前位置交换
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
int main() {
int arr[] = {5, 2, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
selectionSort(arr, n);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]); // 输出 1 2 5 5 9
}
return 0;
}代码逻辑：
-
外层循环：遍历数组，每轮确定一个最小值的位置。
-
内层循环：在未排序部分中找到最小值的位置
minIndex。 -
交换操作：将最小值与当前未排序部分的第一个元素交换。
-
时间复杂度：O(n²)。
解法3：快速排序（难度★★★）
通俗解释：
-
像“分而治之”，选一个基准值，小的放左边，大的放右边，递归处理左右子数组。
c
#include <stdio.h>
// 分区函数：将数组分为左右两部分，返回基准值的位置
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // 选最后一个元素作为基准值
int i = low - 1; // 指向比基准值小的区域的末尾
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
// 交换元素，将小的值移到左边
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 将基准值放到正确位置
int temp = arr[i+1];
arr[i+1] = arr[high];
arr[high] = temp;
return i + 1;
}
// 递归排序函数
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high); // 获取基准值位置
quickSort(arr, low, pi - 1); // 排序左半部分
quickSort(arr, pi + 1, high); // 排序右半部分
}
}
int main() {
int arr[] = {5, 2, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n-1);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]); // 输出 1 2 5 5 9
}
return 0;
}代码逻辑：
-
分区函数：
-
选择基准值
pivot（通常选最后一个元素）。 -
遍历数组，将小于
pivot的元素移到左侧。 -
最后将
pivot放到中间位置。
-
-
递归排序：
-
对基准值左侧和右侧的子数组递归调用快速排序。
-
-
时间复杂度：平均 O(n log n)，最坏 O(n²)。
四、C++实现
解法1：使用STL的sort函数（难度★☆）
通俗解释：
-
直接调用C++标准库的排序函数，一行代码完成排序。
cpp
#include <iostream>
#include <algorithm> // 包含sort函数
#include <vector>
using namespace std;
int main() {
vector<int> vec = {5, 2, 9, 1, 5};
sort(vec.begin(), vec.end()); // 默认升序排序
for (int num : vec) {
cout << num << " "; // 输出 1 2 5 5 9
}
return 0;
}代码逻辑：
-
sort函数：
-
参数1：起始迭代器（
vec.begin()）。 -
参数2：结束迭代器（
vec.end()）。 -
默认按升序排序，底层实现为快速排序的优化版本（IntroSort）。
-
-
时间复杂度：O(n log n)。
解法2：自定义排序规则（难度★★）
通俗解释：
-
按绝对值排序或降序排序，需自定义比较函数。
cpp
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
// 自定义比较函数：按绝对值升序
bool compareAbs(int a, int b) {
return abs(a) < abs(b);
}
int main() {
vector<int> vec = {-3, 1, -5, 4};
sort(vec.begin(), vec.end(), compareAbs); // 传入自定义比较函数
for (int num : vec) {
cout << num << " "; // 输出 1 -3 4 -5
}
return 0;
}代码逻辑：
-
比较函数：
-
若
compare(a, b)返回true，则a排在b前面。 -
此处按绝对值升序排列。
-
-
函数传递：将函数名
compareAbs作为参数传递给sort。
解法3：归并排序（难度★★★）
通俗解释：
-
将数组分成两半，分别排序后合并。
cpp
#include <iostream>
#include <vector>
using namespace std;
// 合并两个有序数组
void merge(vector<int>& arr, int left, int mid, int right) {
vector<int> temp(right - left + 1);
int i = left, j = mid + 1, k = 0;
// 比较两个子数组的元素，依次放入临时数组
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
// 将剩余元素复制到临时数组
while (i <= mid) temp[k++] = arr[i++];
while (j <= right) temp[k++] = arr[j++];
// 将临时数组拷贝回原数组
for (int p = 0; p < k; p++) {
arr[left + p] = temp[p];
}
}
// 递归排序函数
void mergeSort(vector<int>& arr, int left, int right) {
if (left >= right) return;
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid); // 排序左半部分
mergeSort(arr, mid + 1, right); // 排序右半部分
merge(arr, left, mid, right); // 合并两部分
}
int main() {
vector<int> vec = {5, 2, 9, 1, 5};
mergeSort(vec, 0, vec.size() - 1);
for (int num : vec) {
cout << num << " "; // 输出 1 2 5 5 9
}
return 0;
}代码逻辑：
-
分治思想：
-
递归将数组分成两半，直到每个子数组只有一个元素。
-
合并两个有序子数组。
-
-
合并操作：
-
创建临时数组存储合并结果。
-
比较两个子数组的元素，按序放入临时数组。
-
-
时间复杂度：O(n log n)。
五、总结对比表
| 方法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 |
|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(1) | 简单直观 | 效率低，仅适合小数据 |
| 选择排序 | O(n²) | O(1) | 简单，交换次数少 | 效率低 |
| 快速排序 | O(n log n) 平均 | O(log n) | 高效，适合大数据 | 最坏情况O(n²) |
| STL sort | O(n log n) | O(log n) | 极简代码，高效 | 依赖STL库 |
| 归并排序 | O(n log n) | O(n) | 稳定排序，适合链表 | 需要额外空间 |
->返回c/c++蓝桥杯经典编程题100道-目录