C++算法：排序概念和稳定性教程

1. 排序的基本概念

排序是计算机科学中一项基础且重要的操作，它的目的是将一组数据按照特定的顺序（通常是升序或降序）重新排列。例如，将一组整数 {5, 3, 8, 1, 2} 按照升序排列后变为 {1, 2, 3, 5, 8}。排序在很多场景中都有广泛应用，比如在数据库中对查询结果进行排序，在搜索引擎中对搜索结果进行排序等。

2. 排序算法的稳定性

排序算法的稳定性是指在排序过程中，相等元素的相对顺序是否保持不变。如果一个排序算法能够保证相等元素的相对顺序不变，那么这个排序算法就是稳定的；反之，则是不稳定的。

例如，有一组学生数据，每个学生有姓名和成绩两个属性，现在要按照成绩对学生进行排序。如果有两个学生 A 和 B 的成绩相同，在排序前 A 在 B 前面，经过排序后 A 仍然在 B 前面，那么这个排序算法就是稳定的；如果排序后 B 到了 A 前面，那么这个排序算法就是不稳定的。

3. 常见排序算法的稳定性分析

3.1 冒泡排序（Bubble Sort）

冒泡排序是一种简单的排序算法，它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

#include <iostream>
#include <vector>

// 冒泡排序函数
void bubbleSort(std::vector<int>& arr) {
    int n = arr.size();
    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;
            }
        }
    }
}

int main() {
    std::vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
    bubbleSort(arr);
    std::cout << "Sorted array: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

稳定性分析：冒泡排序是稳定的排序算法。因为在比较相邻元素时，如果它们相等，是不会进行交换的，所以相等元素的相对顺序不会改变。

3.2 选择排序（Selection Sort）

选择排序是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。

#include <iostream>
#include <vector>

// 选择排序函数
void selectionSort(std::vector<int>& arr) {
    int n = arr.size();
    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;
            }
        }
        // 交换 arr[i] 和 arr[minIndex]
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

int main() {
    std::vector<int> arr = {64, 25, 12, 22, 11};
    selectionSort(arr);
    std::cout << "Sorted array: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

稳定性分析：选择排序是不稳定的排序算法。例如，有一组数据 {5, 8, 5, 2}，在第一次选择最小元素时，会将第一个 5 和 2 交换位置，这样就改变了两个 5 的相对顺序。

3.3 插入排序（Insertion Sort）

插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

#include <iostream>
#include <vector>

// 插入排序函数
void insertionSort(std::vector<int>& arr) {
    int n = arr.size();
    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;
    }
}

int main() {
    std::vector<int> arr = {12, 11, 13, 5, 6};
    insertionSort(arr);
    std::cout << "Sorted array: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

稳定性分析：插入排序是稳定的排序算法。在插入元素时，如果遇到相等元素，会将新元素插入到相等元素的后面，不会改变相等元素的相对顺序。

4. 总结

排序算法的稳定性在某些场景下非常重要，比如在多级排序中，先按照一个属性排序，再按照另一个属性排序时，如果第一个排序算法是稳定的，那么第二个排序可以在第一个排序的基础上进行，而不会破坏第一个排序的结果。在实际应用中，需要根据具体的需求选择合适的排序算法。

以上就是关于 C++ 中排序概念和稳定性的基础教程，希望对你有所帮助。你可以自己动手实现这些排序算法，并测试它们的稳定性。