数组排序

->返回c/c++蓝桥杯经典编程题100道-目录

---

目录

数组排序

一、题型解释

二、例题问题描述

三、C语言实现

解法1：冒泡排序（难度★）

解法2：选择排序（难度★）

解法3：快速排序（难度★★★）

四、C++实现

解法1：使用STL的sort函数（难度★☆）

解法2：自定义排序规则（难度★★）

解法3：归并排序（难度★★★）

五、总结对比表

---

一、题型解释

数组排序是将数组元素按特定顺序（升序、降序或自定义规则）重新排列的操作。常见题型：

1. 基础排序：将数组按升序或降序排列（如 [3,1,4] → [1,3,4]）。

2. 稳定排序：相同元素的相对顺序不变（如按姓名排序后，同分学生的顺序不变）。

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;
}

代码逻辑：

1. 外层循环：共进行 n-1 轮（每轮确定一个最大值的位置）。

2. 内层循环：每轮比较相邻元素，若前大后小则交换。

3. 优化：第 i 轮时，末尾 i 个元素已有序，无需再比较。

4. 时间复杂度：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;
}

代码逻辑：

1. 外层循环：遍历数组，每轮确定一个最小值的位置。

2. 内层循环：在未排序部分中找到最小值的位置 minIndex。

3. 交换操作：将最小值与当前未排序部分的第一个元素交换。

4. 时间复杂度：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;
}

代码逻辑：

1. 分区函数：

   • 选择基准值 pivot（通常选最后一个元素）。

   • 遍历数组，将小于 pivot 的元素移到左侧。

   • 最后将 pivot 放到中间位置。

2. 递归排序：

   • 对基准值左侧和右侧的子数组递归调用快速排序。

3. 时间复杂度：平均 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;
}

代码逻辑：

1. sort函数：

   • 参数1：起始迭代器（vec.begin()）。

   • 参数2：结束迭代器（vec.end()）。

   • 默认按升序排序，底层实现为快速排序的优化版本（IntroSort）。

2. 时间复杂度：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;
}

代码逻辑：

1. 比较函数：

   • 若 compare(a, b) 返回 true，则 a 排在 b 前面。

   • 此处按绝对值升序排列。

2. 函数传递：将函数名 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;
}

代码逻辑：

1. 分治思想：

   • 递归将数组分成两半，直到每个子数组只有一个元素。

   • 合并两个有序子数组。

2. 合并操作：

   • 创建临时数组存储合并结果。

   • 比较两个子数组的元素，按序放入临时数组。

3. 时间复杂度：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道-目录