在C++编程中，short int是常用的短整型数据类型，占用2字节内存空间，取值范围有限。当我们需要对存储short int元素的数组进行排序时，有多种算法可以选择，不同算法在时间复杂度、空间复杂度和实现难度上各有差异。
常见的short int数组排序方法
1. 冒泡排序
冒泡排序是最基础的排序算法之一，核心逻辑是通过相邻元素的比较和交换，让较大的元素逐步移动到数组末尾，整个过程类似气泡上浮。该算法实现简单，适合小规模数组排序。
#include <iostream>
using namespace std;
// 冒泡排序实现short int数组排序
void bubbleSort(short int arr[], int length) {
for (int i = 0; i < length - 1; i++) {
// 标记是否发生交换，优化排序效率
bool swapped = false;
for (int j = 0; j < length - 1 - i; j++) {
// 相邻元素比较，逆序则交换
if (arr[j] > arr[j + 1]) {
short int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// 如果没有发生交换，说明数组已经有序，提前退出循环
if (!swapped) {
break;
}
}
}
int main() {
short int testArr[] = {5, 2, 9, 1, 5, 6};
int arrLength = sizeof(testArr) / sizeof(testArr[0]);
cout << "排序前数组：";
for (int i = 0; i < arrLength; i++) {
cout << testArr[i] << " ";
}
cout << endl;
bubbleSort(testArr, arrLength);
cout << "冒泡排序后数组：";
for (int i = 0; i < arrLength; i++) {
cout << testArr[i] << " ";
}
cout << endl;
return 0;
}
2. 快速排序
快速排序是效率较高的排序算法，采用分治思想，选择一个基准元素将数组分为两部分，左边部分元素都小于基准，右边部分都大于基准，再递归处理两部分子数组。平均时间复杂度为O(n log n)，适合中大规模数组排序。
#include <iostream>
using namespace std;
// 快速排序分区函数，返回基准元素最终位置
int partition(short int arr[], int low, int high) {
short int pivot = arr[high]; // 选择最后一个元素作为基准
int i = low - 1; // 小于基准的元素边界
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
// 交换元素到小于基准的区域
short int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 将基准元素放到正确位置
short int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
// 快速排序递归实现
void quickSort(short 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() {
short int testArr[] = {3, 7, 2, 8, 1, 4, 6, 5};
int arrLength = sizeof(testArr) / sizeof(testArr[0]);
cout << "排序前数组：";
for (int i = 0; i < arrLength; i++) {
cout << testArr[i] << " ";
}
cout << endl;
quickSort(testArr, 0, arrLength - 1);
cout << "快速排序后数组：";
for (int i = 0; i < arrLength; i++) {
cout << testArr[i] << " ";
}
cout << endl;
return 0;
}
3. 标准库sort函数排序
C++标准库提供了sort函数，位于<algorithm>头文件中，内部通常采用高效的混合排序算法，使用起来非常方便，不需要手动实现排序逻辑，是实际开发中最推荐的排序方式。
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
short int testArr[] = {10, 3, 8, 1, 9, 2, 7, 4, 6, 5};
int arrLength = sizeof(testArr) / sizeof(testArr[0]);
cout << "排序前数组：";
for (int i = 0; i < arrLength; i++) {
cout << testArr[i] << " ";
}
cout << endl;
// 调用标准库sort函数排序short int数组
sort(testArr, testArr + arrLength);
cout << "标准库sort排序后数组：";
for (int i = 0; i < arrLength; i++) {
cout << testArr[i] << " ";
}
cout << endl;
return 0;
}
不同排序方法对比
以下是三种排序方法的特性对比，方便开发者根据场景选择：
| 排序方法 | 平均时间复杂度 | 空间复杂度 | 实现难度 | 适用场景 |
|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(1) | 简单 | 小规模数组、教学演示 |
| 快速排序 | O(n log n) | O(log n) | 中等 | 中大规模数组、自定义排序逻辑 |
| 标准库sort | O(n log n) | O(log n) | 简单 | 实际开发、无特殊排序需求 |
注意事项
- short int数组的长度需要准确计算，避免使用越界访问导致程序异常
- 如果数组中存在大量重复元素，快速排序的性能可能会下降，此时可以考虑优化分区逻辑
- 标准库
sort函数默认是升序排序，如果需要降序排序，可以传入自定义的比较函数 - 手动实现排序算法时，注意临时变量的类型要和数组元素类型一致，避免数据截断问题
C++_short_int数组排序冒泡排序快速排序修改时间：2026-06-21 12:45:33