C++ 数组排序

在编程中，排序是一种非常常见且重要的操作。无论是对用户数据进行展示，还是为了后续的数据处理（如二分查找），掌握数组排序方法都是每位程序员必备的基本技能。本文将介绍几种在C++中对数组进行排序的方法。

为什么需要排序？

在我们深入了解排序算法之前，先思考一下为什么需要排序：

1. 提高搜索效率：在有序数组中使用二分查找，时间复杂度为 O(log n)
2. 数据展示：按照特定顺序（如字母顺序、数值大小）展示数据
3. 数据分析：排序后更容易找出最大值、最小值、中位数等统计数据
4. 去重操作：排序后相同元素会相邻，便于去除重复元素

基础排序算法

1. 冒泡排序 (Bubble Sort)

冒泡排序是最简单的排序算法之一，它重复地遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就交换他们的位置。

cpp

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]) {
                // 交换 arr[j] 和 arr[j+1]
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

示例：

cpp

#include <iostream>
using namespace std;

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]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    cout << "排序前的数组: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
    
    bubbleSort(arr, n);
    
    cout << "排序后的数组: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
    
    return 0;
}

输出：

排序前的数组: 64 34 25 12 22 11 90
排序后的数组: 11 12 22 25 34 64 90

备注

冒泡排序的时间复杂度为 O(n²)，其中 n 是数组的长度。对于大型数组，这种方法效率较低。

2. 选择排序 (Selection Sort)

选择排序是一种简单直观的排序算法，它的工作原理是每次从待排序数列中找出最小（或最大）的元素，放在已排序序列的末尾。

cpp

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        // 找出从i到n-1中的最小值的索引
        int min_idx = i;
        for (int j = i+1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        
        // 将找到的最小值放在正确的位置
        int temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;
    }
}

示例：

cpp

#include <iostream>
using namespace std;

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;
            }
        }
        
        int temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;
    }
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    cout << "排序前的数组: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
    
    selectionSort(arr, n);
    
    cout << "排序后的数组: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
    
    return 0;
}

输出：

排序前的数组: 64 25 12 22 11
排序后的数组: 11 12 22 25 64

3. 插入排序 (Insertion Sort)

插入排序的工作方式类似于我们排序一手扑克牌。开始时，我们的左手为空并且桌子上的牌面朝下。然后，我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到正确的位置，我们从右到左将它与已在手中的每张牌进行比较。

cpp

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        
        // 将比key大的元素向右移动
        while (j >= 0 && arr[j] > key) {
            arr[j+1] = arr[j];
            j = j - 1;
        }
        arr[j+1] = key;
    }
}

示例：

cpp

#include <iostream>
using namespace std;

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 = j - 1;
        }
        arr[j+1] = key;
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    cout << "排序前的数组: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
    
    insertionSort(arr, n);
    
    cout << "排序后的数组: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
    
    return 0;
}

输出：

排序前的数组: 12 11 13 5 6
排序后的数组: 5 6 11 12 13

使用C++ STL排序

C++标准模板库(STL)提供了一个强大的排序函数sort()，它实现了一种改进的快速排序算法，能够高效地对各种数据类型进行排序。

使用 std::sort

cpp

#include <algorithm>  // 包含sort函数的头文件

// 使用方法
sort(起始迭代器, 结束迭代器);

示例：

cpp

#include <iostream>
#include <algorithm>  // 为了使用sort函数
using namespace std;

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    cout << "排序前的数组: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
    
    // 使用STL的sort函数
    sort(arr, arr + n);
    
    cout << "排序后的数组: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
    
    return 0;
}

输出：

排序前的数组: 64 25 12 22 11
排序后的数组: 11 12 22 25 64

提示

std::sort 函数的时间复杂度为 O(n log n)，这比前面介绍的简单排序算法要快得多。对于大多数实际应用，你应该优先使用这个函数。

自定义排序顺序

std::sort 函数还允许你指定一个自定义的比较函数来控制排序顺序。

cpp

#include <iostream>
#include <algorithm>
using namespace std;

// 自定义比较函数：降序排列
bool compare(int a, int b) {
    return a > b;  // 返回true时，a应该排在b前面
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    cout << "排序前的数组: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
    
    // 使用自定义比较函数进行降序排序
    sort(arr, arr + n, compare);
    
    cout << "降序排序后的数组: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
    
    return 0;
}

输出：

排序前的数组: 64 25 12 22 11
降序排序后的数组: 64 25 22 12 11

实际应用案例

学生成绩排序系统

假设我们需要开发一个简单的学生成绩管理系统，按照成绩对学生进行排序。

cpp

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;

// 定义学生结构体
struct Student {
    string name;
    int score;
};

// 自定义比较函数：按成绩降序排列
bool compareByScore(const Student& a, const Student& b) {
    return a.score > b.score;
}

int main() {
    // 创建学生数组
    vector<Student> students = {
        {"张三", 85},
        {"李四", 92},
        {"王五", 78},
        {"赵六", 95},
        {"钱七", 88}
    };
    
    cout << "排序前的学生列表：" << endl;
    for (const auto& student : students) {
        cout << student.name << ": " << student.score << endl;
    }
    
    // 按成绩排序
    sort(students.begin(), students.end(), compareByScore);
    
    cout << "\n按成绩降序排序后的学生列表：" << endl;
    for (const auto& student : students) {
        cout << student.name << ": " << student.score << endl;
    }
    
    return 0;
}

输出：

排序前的学生列表：
张三: 85
李四: 92
王五: 78
赵六: 95
钱七: 88

按成绩降序排序后的学生列表：
赵六: 95
李四: 92
钱七: 88
张三: 85
王五: 78

字符串数组排序

在很多应用中，我们经常需要对字符串数组进行排序，例如字典、联系人列表等。

cpp

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    vector<string> names = {"David", "Alice", "Charlie", "Bob", "Eva"};
    
    cout << "排序前的名字：" << endl;
    for (const auto& name : names) {
        cout << name << endl;
    }
    
    // 按字母顺序排序
    sort(names.begin(), names.end());
    
    cout << "\n按字母顺序排序后的名字：" << endl;
    for (const auto& name : names) {
        cout << name << endl;
    }
    
    return 0;
}

输出：

排序前的名字：
David
Alice
Charlie
Bob
Eva

按字母顺序排序后的名字：
Alice
Bob
Charlie
David
Eva

总结

在C++中对数组进行排序是一项基础但重要的操作。我们学习了几种不同的排序算法：

1. 冒泡排序：简单但效率较低，时间复杂度为O(n²)
2. 选择排序：思想简单明了，仍然是O(n²)复杂度
3. 插入排序：对于小数组或几乎已排序的数组效果较好
4. STL的sort函数：基于改进的快速排序，时间复杂度为O(n log n)，是实际应用中的首选

对于大多数情况，建议使用C++ STL提供的sort函数，因为它经过了优化，性能出色。只有在特定场景下（如教学目的、资源极度受限、或特殊需求），才需要考虑实现自定义排序算法。

警告

请记住，排序算法的选择应该基于具体的应用场景、数据规模和性能要求。没有一种排序算法在所有情况下都是最佳选择。

练习题

1. 编写程序，使用冒泡排序对10个随机生成的整数进行排序。
2. 实现一个函数，可以对字符串数组进行排序，但不区分大小写。
3. 创建一个结构体表示商品（包含名称、价格、库存），然后编写程序按照价格对商品进行排序。
4. 尝试使用std::sort函数对一个包含100万个随机整数的数组进行排序，并测量所需时间。
5. 修改冒泡排序算法，使其能够提前终止（当某一轮没有发生交换时，说明数组已排序）。

通过这些练习，你将更好地掌握C++数组排序的各种方法和应用。